Space Complexity

Space-bounded Computation#

Two variants: deterministic and nondeterministic.

Definition. Let \(s:\N\to\N\) and \(L\subseteq\{0,1\}^\ast\). We say that \(L\in\mathbf{SPACE}(s(n))\) if there is a constant \(c\) and a Turing machine \(M\) deciding \(L\) such that at most \(c\cdot s(n)\) locations on \(M\)'s works tapes (excluding the input tape) are ever visited by \(M\)'s head during its computation on every input of \(n\).

Definition. Let \(s:\N\to\N\) and \(L\subseteq\{0,1\}^\ast\). We say that \(L\in\mathbf{NSPACE}(s(n))\) if there is a constant \(c\) and a nondeterministic Turing machine \(M\) deciding \(L\) that uses at most \(c\cdot s(n)\) locations on \(M\)'s nonblank tapes (excluding the input tape) are ever used during its computation on every input of \(n\).

Analogously to time complexity, we restrict our attention to space bounds \(s:\N\to\N\) that are space-constructible, by which we mean that there is a Turing machine that computes \(s(|x|)\) in \(O(s(|x|)\) space given \(x\) as input.

Space- and Time-bounded computations#

The only known relationships between the power of space-bounded and time-bounded computation is the following theorem:

Theorem. For every space constructible \(s:\N\to\N\),
 

\[\text{DTIME}(s(n)) \subseteq \text{SPACE}(s(n))\subseteq \text{NSPACE}(s(n)) \subseteq \text{DTIME}(2^{O(s(n))}).\]

The first inclusion is simple since a Turing machine can access only one tape cell per step, but a \(\text{SPACE}(s(n))\) machine can run for much longer than \(s(n)\) steps, since space can be reused. The second inclusion is trivial. The last one is shown by a configuration graph argument.

Space Hierarchy Theorem#

Completely analogous to the proof of the time hierarchy theorem except that one can have a universal Turing machine using only a constant factor of space overhead, the following theorem can be proved:

Theorem. If \(f\) is a space-constructible function, then
 

\[\text{SPACE}(o(f(n))) \subsetneq \text{SPACE}(f(n)).\]

Some space complexity classes#

Analogously to time complexity classes, we may define

• \(\mathbf{PSPACE} = \bigcup_{k>0} \text{SPACE}(n^k)\) - space analog of the time complexity class \(\mathbf{P}\).
• \(\mathbf{NPSPACE} = \bigcup_{k>0} \text{NSPACE}(n^k)\) - space analog of the time complexity class \(\mathbf{NP}\).
• \(\mathbf{L} = \text{SPACE}(\log n)\) - no analog for time since time bounds shorter than the input length don't make much sense.
• \(\mathbf{NL}=\text{NSPACE}(\log n)\) - no analog for time since time bounds shorter than the input length don't make much sense.

It is still open whether \(\mathbf{NP}\neq \mathbf{L}\), and we know that \(\mathbf{NP}\subseteq \mathbf{PSPACE}\) (by cycling through all potential certificates using the linear space), and even more, \(\mathbf{PSPACE} = \mathbf{NPSPACE}\).

Theorem (Savitch's Theorem). For any space-constructible \(s:\N\to\N\) with \(s(n) \geq \log n\), \(\text{NSPACE}(s(n))\subseteq \text{SPACE}(s(n)^2)\).

Relations between the various space-bounded and time-bounded complexity classes#

\[\mathbf{L} \subseteq \mathbf{NL} \subseteq \mathbf{P} \subseteq \mathbf{NP} \subseteq \mathbf{PSPACE}= \mathbf{NPSPACE} \subseteq \mathbf{EXP}\]

The hierarchy theorems further implies that \(\mathbf{L}\subsetneq \mathbf{PSPSACE}\) and \(\mathbf{P}\subsetneq \mathbf{EXP}\), but we don't know which ones in the above filteration are strict.