7 min read
On this page

Space Complexity

Fundamental Space Classes

DSPACE(f(n)): Languages decidable by a deterministic TM using O(f(n)) work tape cells. NSPACE(f(n)): Languages decidable by a nondeterministic TM using O(f(n)) work tape cells.

Key classes:

  • L = DSPACE(log n): Deterministic logarithmic space
  • NL = NSPACE(log n): Nondeterministic logarithmic space
  • PSPACE = union over k of DSPACE(n^k): Polynomial space
  • NPSPACE = union over k of NSPACE(n^k): Nondeterministic polynomial space

The input tape is read-only and does not count toward space. This is essential for sublinear space classes to be meaningful.

Space Hierarchy Theorem

Theorem: If f(n) is space-constructible and f(n) = o(g(n)), then DSPACE(f(n)) is strictly contained in DSPACE(g(n)).

Unlike the time hierarchy, there is no logarithmic overhead, giving a tight separation. The proof diagonalizes directly: simulate machine M_i on input x using g(n) space, reject if it accepts within space f(n). The tighter result follows because space can be precisely measured and reused (unlike time).

Corollary: L is strictly contained in PSPACE. DSPACE(n) is strictly contained in DSPACE(n^2).

The nondeterministic space hierarchy also holds: NSPACE(f(n)) is strictly contained in NSPACE(g(n)) when f(n) = o(g(n)) and both are space-constructible (follows from Immerman-Szelepcsenyi plus deterministic hierarchy).

Savitch's Theorem

Theorem (Savitch, 1970): NSPACE(f(n)) is contained in DSPACE(f(n)^2) for f(n) >= log n.

Proof sketch: Given an NSPACE(f(n)) machine, the question "does configuration C1 reach C2 in at most 2^k steps?" can be solved recursively: guess a midpoint configuration C_mid and check C1 -> C_mid in 2^{k-1} steps AND C_mid -> C2 in 2^{k-1} steps. Each recursion level stores one configuration (O(f(n)) space), and the recursion depth is O(f(n)), giving O(f(n)^2) total space.

Corollary: PSPACE = NPSPACE. Nondeterminism does not significantly help for polynomial space.

Remark: Savitch's theorem is believed to be tight for general NL. Improving it to NSPACE(f(n)) in DSPACE(f(n)^{2-epsilon}) for any epsilon > 0 would be a breakthrough, implying NL != P (since the directed reachability problem is NL-complete and solvable in polynomial time).

L and NL

L (Deterministic Log-Space)

L captures problems solvable with a constant number of pointers into the input. Key problems in L:

  • Undirected connectivity (Reingold, 2005) -- a celebrated result using zig-zag graph products
  • Evaluating Boolean formulas (tree-shaped circuits)
  • Recognizing regular languages
  • 2-colorability of graphs

L is contained in P because a log-space machine has at most poly(n) configurations, so it halts in polynomial time. More precisely, DSPACE(log n) is contained in DTIME(n^{O(1)}).

NL and NL-Completeness

NL is the class of languages decided by nondeterministic log-space machines. The canonical NL-complete problem is PATH (s-t connectivity in directed graphs).

Log-space reductions: A reduces to B via log-space reduction if there is a function f computable in O(log n) space such that x in A iff f(x) in B. Log-space reductions compose (though this requires care: the composition is computed implicitly).

NL-complete problems:

  • Directed s-t connectivity (PATH)
  • 2SAT (satisfiability)
  • Directed graph reachability on specific graph classes

Theorem: NL is contained in P (since PATH is solvable in polynomial time by BFS/DFS).

The full containment chain: L is contained in NL is contained in P is contained in NP is contained in PSPACE is contained in EXPTIME. At least one containment must be strict (since L != PSPACE by the space hierarchy), but we cannot prove which ones.

Immerman-Szelepcsenyi Theorem

Theorem (Immerman, 1988; Szelepcsenyi, 1988): NL = coNL. More generally, NSPACE(f(n)) = coNSPACE(f(n)) for f(n) >= log n.

This was surprising because NTIME classes are not known to be closed under complement (NP = coNP is a major open question).

Proof technique (inductive counting):

To show PATH-complement is in NL, we need to verify non-reachability in log space. The key idea:

  1. Counting reachable vertices: Compute c_k = |{v : v reachable from s in at most k steps}| for k = 0, 1, ..., n-1.
  2. Inductive step: Given c_k, compute c_{k+1} nondeterministically. For each vertex v, determine if v is reachable in k+1 steps by:
    • For each potential predecessor u, nondeterministically verify whether u is reachable in k steps
    • Count how many reachable vertices are found; verify the count matches c_k
  3. Final check: After computing c_{n-1}, verify that t is NOT among the reachable vertices.

The counter c_k requires O(log n) bits, and at each stage we enumerate vertices (O(log n) bits each). The total space is O(log n).

Consequences: coNL-complete problems (like directed non-reachability) are also in NL. The symmetric closure strengthens the analogy between space and time, but the techniques (counting vs. complementation) are very different.

PSPACE and PSPACE-Completeness

PSPACE captures problems solvable with polynomial working memory, regardless of time. Since a poly-space machine can run for at most 2^{poly(n)} steps, PSPACE is contained in EXPTIME.

TQBF: The Canonical PSPACE-Complete Problem

TQBF (True Quantified Boolean Formulas): Given a fully quantified Boolean formula (forall x1)(exists x2)...(Q x_n) phi(x1,...,xn), is it true?

Theorem (Stockmeyer-Meyer, 1973): TQBF is PSPACE-complete under polynomial-time (in fact, log-space) reductions.

Proof of PSPACE-hardness: Given a PSPACE machine M on input x, encode the computation as: "does there exist a sequence of configurations leading from start to accept?" Each configuration uses poly(n) bits. Quantifier alternation captures the recursive structure of Savitch's reachability algorithm.

Other PSPACE-Complete Problems

  • Generalized games: Generalized chess, Go, Hex (on n x n boards)
  • Regular expression equivalence: Are two regexes equivalent?
  • Stochastic satisfiability: SSAT extends QBF with randomized quantifiers
  • Planning: STRIPS planning (propositional)

The Polynomial Hierarchy and PSPACE

The polynomial hierarchy PH = union over k of Sigma_k^P is contained in PSPACE:

  • Sigma_0^P = Pi_0^P = P
  • Sigma_{k+1}^P = NP^{Sigma_k^P}
  • Pi_{k+1}^P = coNP^{Sigma_k^P}

If PH = PSPACE, then PH collapses (Karp-Lipton-style argument). It is believed that PH is strictly contained in PSPACE, but this is unproven.

TQBF with bounded alternations: Formulas with k quantifier alternations capture Sigma_k^P (or Pi_k^P depending on the leading quantifier).

Space-Bounded Computation and Complements

| Class | Complement | Status | |---|---|---| | L | L | Deterministic classes are trivially closed under complement | | NL | coNL = NL | Immerman-Szelepcsenyi | | P | P | Trivial | | NP | coNP | Open (believed NP != coNP) | | PSPACE | PSPACE | Trivial (PSPACE = NPSPACE = coNPSPACE) |

The contrast between space and time regarding complementation is striking. The inductive counting technique works for space because a space-bounded machine can revisit configurations; a time-bounded machine cannot reuse computation steps.

Logspace Certificates and Characterizations

NL has polynomial-length certificates: A language is in NL iff it has polynomial-length certificates verifiable in log space. This connects NL to a restricted form of NP.

NL = coNL gives two-way certificates: Both membership and non-membership in NL languages have log-space verifiable certificates.

Relationships Between Space and Time

Theorem: DTIME(f(n)) is contained in DSPACE(f(n)/log n) (a time f(n) machine uses at most f(n) tape cells, and with care the log factor can be gained).

Theorem: DSPACE(f(n)) is contained in DTIME(2^{O(f(n))}) (the configuration space is exponential in the space bound).

Theorem (Hopcroft-Paul-Valiant, 1977): DTIME(t(n)) is contained in DSPACE(t(n)/log t(n)).

These results give: L is in P, P is in PSPACE, PSPACE is in EXPTIME, with the hierarchy theorem ensuring at least one strict containment per exponential jump.

Space-Bounded Randomness

  • RL (one-sided error, log space): Contained in L by Reingold's theorem (since USTCON is in L and RL reduces to USTCON for many natural problems). Nisan (1992) showed RL is in DSPACE(log^2 n) unconditionally.
  • BPL (two-sided error, log space): Conjectured to equal L. Saks and Zhou (1999) showed BPL is in DSPACE(log^{3/2} n).

Open Problems

  • Is L = NL? This is analogous to P vs NP but for space.
  • Is NL = P? NL is contained in P, but equality is unknown.
  • Can Savitch's theorem be improved? Is NL in DSPACE(log^{2-epsilon} n)?
  • Does DSPACE(n) = NSPACE(n)? (Even this is open, though Savitch gives NSPACE(n) in DSPACE(n^2).)
  • The L vs P question: are there problems in P not solvable in log space?

Space Complexity Zoo (Selected)

| Class | Definition | Complete Problem | |---|---|---| | L | DSPACE(log n) | -- | | NL | NSPACE(log n) | PATH | | P | DTIME(poly) | Circuit Value Problem | | PSPACE | DSPACE(poly) | TQBF | | EXPSPACE | DSPACE(2^{poly}) | Equivalence of regexes with squaring |