A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Space complexity measures the number of tape cells a TM uses on an input of length n. PSPACE is the class of problems solvable in polynomial space; it contains both P and NP and is known to contain problems harder than any fixed polynomial. L and NL are the classes solvable in O(log n) space deterministically and nondeterministically; NL contains graph reachability (STCON). Savitch's theorem shows that nondeterministic space S(n) ≥ log n can be simulated deterministically in S(n)² space, so NPSPACE = PSPACE — a striking contrast to the unresolved P vs. NP question.
Contrast space with time: space can be reused across computation steps but time cannot. Work through Savitch's theorem to see why nondeterministic and deterministic space are polynomially related, while the analogous time question (NP ⊆ P?) remains open. Study QBF satisfiability as the canonical PSPACE-complete problem.
When we measure complexity by time, we count computation steps. Space complexity counts something different: the number of distinct tape cells written during the computation. The crucial difference is that space is *reusable* — after a machine finishes using part of the tape for an intermediate result, it can overwrite those cells. Time does not share this property; each step is consumed and cannot be revisited. This asymmetry is what makes space complexity behave so differently from time complexity.
PSPACE is the class of problems solvable using at most a polynomial number of tape cells. It contains both P and NP — any nondeterministic polynomial-time computation uses at most polynomial space — but PSPACE may contain harder problems still. The canonical PSPACE-complete problem is QBF (Quantified Boolean Formula satisfiability): determining the truth of a fully quantified Boolean formula such as ∀x∃y(x ∨ y). Solving QBF requires systematically exploring all assignments under alternating quantifiers, which is believed to require super-polynomial time despite using only polynomial space.
Savitch's theorem establishes a striking result: NPSPACE = PSPACE. Any nondeterministic machine using S(n) ≥ log n space can be simulated by a deterministic machine using O(S(n)²) space. The simulation works by a recursive divide-and-conquer: "can configuration A reach configuration B in k steps?" is answered by guessing a midpoint configuration M and recursively asking "can A reach M in k/2 steps?" and "can M reach B in k/2 steps?" Each recursive call reuses the same space, keeping total usage polynomial. Crucially, this technique cannot be applied to time because each recursive sub-call requires its own time steps — they cannot be reused or shared.
L and NL are the log-space classes, and they sit at the other end of the spectrum from PSPACE. L allows only O(log n) bits on the working tape — enough to store O(1) pointers into the input, but not enough to copy it. This is surprisingly powerful: O(log n) bits can represent any index from 0 to n-1, so a log-space machine can navigate the input freely using a handful of counters. NL adds nondeterminism and contains graph reachability (STCON): a nondeterministic log-space machine solves reachability by guessing one node at a time along the path, keeping only the current node in memory.
These classes fit into a containment hierarchy: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP. At least one of these containments is strict (PSPACE ⊊ EXP), but most boundaries — including P vs. NP and NL vs. P — remain unproven. Space complexity adds depth to the complexity landscape, revealing that the central open questions about hardness are just the most visible part of a much larger web of unresolved separations.