Space Complexity
Prerequisite:
Time is not the only scarce resource a computation consumes. Space - the amount of memory a machine uses - gives rise to its own rich hierarchy of complexity classes, with striking structural results that have no direct time analogues. Savitch’s theorem and the Immerman-Szelepcsényi theorem are among the deepest theorems in complexity theory, and they reveal a world where nondeterminism buys far less than it does in the time setting.
Defining Space Complexity
We measure space on a multi-tape Turing machine where the input tape is read-only. Only the work tape cells count toward the space bound, allowing sublinear space classes to be defined cleanly.
Definition. A language $L \in \text{DSPACE}(s(n))$ if there exists a deterministic Turing machine that decides $L$ using at most $O(s(n))$ work tape cells on inputs of length $n$.
Definition. $L \in \text{NSPACE}(s(n))$ if there exists a nondeterministic TM deciding $L$ within $O(s(n))$ space.
The principal space complexity classes are:
$$L = \text{DSPACE}(\log n), \quad NL = \text{NSPACE}(\log n)$$ $$\text{PSPACE} = \bigcup_{k \geq 1} \text{DSPACE}(n^k), \quad \text{NPSPACE} = \bigcup_{k \geq 1} \text{NSPACE}(n^k)$$
Savitch’s Theorem
The most surprising fact about space complexity is that nondeterminism provides at most a quadratic advantage - far weaker than the conjectured exponential gap in the time setting.
Theorem (Savitch, 1970). For $s(n) \geq \log n$:
$$\text{NSPACE}(s(n)) \subseteq \text{DSPACE}(s(n)^2)$$
In particular, $\text{NPSPACE} = \text{PSPACE}$.
Proof. We reduce reachability in the configuration graph to iterated path-doubling. Define the predicate $\text{REACH}(C, C', t)$ = “there is a path from configuration $C$ to $C'$ in at most $t$ steps.” The base case is trivial. The recursion is:
$$\text{REACH}(C, C', 2^k) = \exists C_m : \text{REACH}(C, C_m, 2^{k-1}) \wedge \text{REACH}(C_m, C', 2^{k-1})$$
A deterministic machine computes $\text{REACH}$ by trying all $2^{O(s(n))}$ possible midpoints $C_m$, recursing to depth $O(s(n))$. Each recursive call reuses the same $O(s(n))$ work tape cells. The recursion depth is $O(s(n))$, and at each level we store a configuration using $O(s(n))$ bits. Total space: $O(s(n)) \cdot O(s(n)) = O(s(n)^2)$. $\square$
The key insight is that nondeterminism in space allows guessing paths, but a deterministic machine can simulate this by systematically enumerating midpoints - using space polynomial in the nondeterministic bound.
The Space Hierarchy Theorem
Space classes form a strict hierarchy when the bound grows by more than a constant factor.
Theorem (Space Hierarchy). If $s_1(n) = o(s_2(n))$ and $s_2(n) \geq \log n$ is space-constructible, then
$$\text{DSPACE}(s_1(n)) \subsetneq \text{DSPACE}(s_2(n))$$
The proof uses diagonalisation: construct a machine that uses exactly $s_2(n)$ space and differs from every machine using $o(s_2(n))$ space on some input. This is cleaner than the time hierarchy because space is reusable - a machine can loop in the same cells, making counting arguments exact.
PSPACE-Completeness: QBF
Definition. A Quantified Boolean Formula (QBF) is a fully quantified formula:
$$\Phi = Q_1 x_1 ; Q_2 x_2 ; \cdots ; Q_n x_n ; \varphi(x_1, \ldots, x_n)$$
where each $Q_i \in {\forall, \exists}$ and $\varphi$ is a Boolean formula.
Theorem. TQBF (True Quantified Boolean Formulas) is PSPACE-complete.
Membership in PSPACE. Evaluate $\Phi$ recursively: for $\exists x_i$, try both $x_i = 0$ and $x_i = 1$ and accept if either sub-formula holds; for $\forall x_i$, require both to hold. The recursion depth is $n$ and each level uses $O(1)$ additional space, so total space is $O(n^2)$ - polynomial.
PSPACE-hardness. Given a PSPACE machine $M$ and input $x$, encode $M$’s computation as a QBF. Alternating quantifiers capture the alternating existential/universal choices naturally. Every language in PSPACE reduces to TQBF in polynomial time.
QBF is to PSPACE as SAT is to NP: the canonical complete problem whose hardness reflects the power of alternation.
Logspace: L and NL
At the low end of the space hierarchy sit the logspace classes, capturing problems solvable with extremely limited memory.
Definition. $L = \text{DSPACE}(\log n)$ and $NL = \text{NSPACE}(\log n)$.
A $\log$-space machine can store $O(\log n)$ bits - enough for a constant number of pointers into the input, but not a copy of the input itself. Graph algorithms in $L$ must be extraordinarily careful.
NL-completeness: ST-Connectivity (STCON).
The problem STCON (given a directed graph $G$ and vertices $s, t$, is $t$ reachable from $s$?) is NL-complete under logspace reductions.
- STCON $\in$ NL. Nondeterministically walk from $s$: at each step, guess the next vertex and check adjacency. Accept if $t$ is reached within $n$ steps. This uses $O(\log n)$ space (to store current vertex and step count).
- NL-hardness. Given any NL machine $M$ and input $x$, build the configuration graph of $M$ on $x$ in logspace. Each configuration is a node; transitions are edges. Reachability from the initial to an accepting configuration equals acceptance of $x$.
Immerman-Szelepcsényi: NL = co-NL
One of the most elegant results in complexity theory is that nondeterministic logspace is closed under complement - something that is open for NP.
Theorem (Immerman 1988, Szelepcsényi 1988). $NL = \text{co-}NL$.
Proof sketch. It suffices to show that non-reachability (the complement of STCON) is in NL. The key is to count the number of vertices reachable from $s$ using a nondeterministic inductive argument.
Define $r_i$ = number of vertices reachable from $s$ in at most $i$ steps. Base case: $r_0 = 1$. At stage $i+1$, a NL machine can verify that $r_{i+1}$ has a specific value $c$ by:
- Guessing, for each vertex $v$, whether it is reachable in $\leq i+1$ steps.
- For each claimed-reachable $v$, nondeterministically verifying reachability.
- Counting claimed-reachable vertices; accepting if the count matches $c$.
The machine maintains only counters of size $O(\log n)$ and a pointer into the vertex list - all logspace. To test non-reachability of $t$, run this protocol to certify $r_n$, and in parallel verify that $t$ was never counted as reachable.
The counting argument is the key: nondeterminism allows guessing witnesses for existence, and by inductively knowing the exact count from the previous round, the machine can verify completeness of the guesses. $\square$
The Space-Time Relationship
Space and time are related by two fundamental inclusions.
Theorem. For any $t(n) \geq n$: $$\text{DTIME}(t(n)) \subseteq \text{DSPACE}(t(n))$$
Proof. A $t(n)$-time machine visits at most $t(n)$ cells. $\square$
Theorem. For any space-constructible $s(n) \geq \log n$: $$\text{DSPACE}(s(n)) \subseteq \text{DTIME}(2^{O(s(n))})$$
Proof. A machine with $s(n)$ space has at most $2^{O(s(n))}$ distinct configurations. It must halt before revisiting a configuration (or it loops forever). $\square$
Combining these gives the full containment chain:
$$L \subseteq NL \subseteq P \subseteq NP \subseteq \text{PSPACE} \subseteq \text{EXPTIME}$$
All containments are believed strict, but only $L \subsetneq \text{PSPACE}$ and $\text{PSPACE} \subsetneq \text{EXPTIME}$ are known to be strict (by the hierarchy theorems).
Examples
Model checking. Given a Kripke structure $M$ and a temporal logic formula $\varphi$ (e.g. CTL*, LTL), does $M \models \varphi$? LTL model checking is PSPACE-complete. The quantifier alternation in temporal logic directly mirrors the alternating quantifiers in QBF.
Two-player game problems. Determining who wins a two-player game with perfect information and polynomial-length play is typically PSPACE-complete. Examples include generalized geography, Hex, and Othello on $n \times n$ boards. The existential player guesses moves; the universal player must be handled for all responses - exactly the QBF quantifier structure.
Logspace graph algorithms. Undirected ST-connectivity is in $L$ (Reingold 2008), showing that even symmetric reachability can be decided with $O(\log n)$ space. The algorithm constructs an expander walk and does not require DFS, which would need $O(n)$ space for the stack.
Read Next: