Time is not the only resource that matters. An algorithm may be fast but need too much memory, or slow but frugal. Space complexity studies how much memory is needed to solve a problem. The results differ from, and in some ways are sharper than, those about time: space can be reused, whereas time, once spent, is gone. This simple observation changes a great deal.
The definitions
For a Turing machine that halts on every input, the space used is the maximum number of tape cells visited on an input of length n.
- SPACE(f(n)): languages decided by a deterministic machine in O(f(n)) space.
- NSPACE(f(n)): the same for nondeterministic machines, where every branch uses at most that space.
- PSPACE: the union of SPACE(nᵏ) over all k, that is the problems solvable with polynomial memory.
For sublinear space, such as log n, a two-tape model is used: a read-only input tape, which is not counted, and a work tape, which is the only one measured. Otherwise just reading the input would take n cells.
Relations with time
Two observations connect time and space:
- Space does not exceed time. In t steps a machine visits at most t cells. So P ⊆ PSPACE and NP ⊆ PSPACE.
- Time is at most exponential in space. A machine using s cells has a number of distinct configurations bounded by 2^O(s). If it halts, it cannot repeat a configuration, or it would loop. So PSPACE ⊆ EXPTIME.
Putting it all together:
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
We know that P ≠ EXPTIME, but not which of the intermediate inclusions is strict.
Why NP is in PSPACE
The first point can also be seen directly for SAT. Try all 2ⁿ assignments one after another, always reusing the same space: write an assignment, evaluate the formula, erase it and move to the next. Time is exponential, but memory stays linear.
Savitch's theorem
For time we do not know whether nondeterminism can be removed at polynomial cost. For space we do:
for every f(n) ≥ log n, NSPACE(f(n)) ⊆ SPACE(f(n)²).
Nondeterminism costs at most a square in space. Consequently PSPACE = NPSPACE.
The idea of the proof
We want to know whether a nondeterministic machine can go from the initial configuration to the accepting one in at most t steps. Define a procedure REACH(c₁, c₂, t):
- if t = 1, check directly whether c₂ follows from c₁ in one step;
- otherwise, for every possible intermediate configuration m: - if REACH(c₁, m, t/2) and REACH(m, c₂, t/2) are both true, answer yes;
- if no m works, answer no.
The time is huge, because every intermediate configuration is tried. But the space is modest: the recursion depth is log t, and each level stores only a few configurations of size O(f(n)). Since t is at most 2^O(f(n)), the depth is O(f(n)) and the total space O(f(n)²).
The key point is that the two recursive calls reuse the same space: run the first, erase its work, then run the second.
A PSPACE-complete problem: TQBF
A fully quantified Boolean formula has every variable bound by a quantifier:
∀x ∃y [(x ∨ y) ∧ (¬x ∨ ¬y)]
This formula is true: for every value of x there is a y, its opposite, that satisfies the bracketed part.
TQBF = {⟨φ⟩ : φ is a true fully quantified Boolean formula}
TQBF is PSPACE-complete: it is in PSPACE and every problem in PSPACE reduces to it in polynomial time.
- TQBF ∈ PSPACE: evaluate recursively. For ∃x try x = 0 and x = 1 and one success is enough; for ∀x both must succeed. The recursion depth is the number of variables, and each level uses constant space.
- Completeness: the reduction reuses the idea of Savitch's theorem, encoding the REACH procedure with quantifiers that avoid duplicating the formula at every level.
The link with games
The alternation ∃∀∃∀ resembles a two-player game: "there is a move of mine such that for every reply of yours there is a move of mine…". This is why many generalized games on an n × n board are PSPACE-complete or even harder. A classic example is generalized geography: on a directed graph the two players take turns moving a token along edges without revisiting a node, and whoever cannot move loses. Deciding whether the first player has a winning strategy is PSPACE-complete.
Logarithmic space: L and NL
At the opposite extreme are the classes with tiny memory:
- L = SPACE(log n): a few counters and pointers into the input are enough;
- NL = NSPACE(log n): the nondeterministic version.
Reachability in a directed graph is NL-complete. By Savitch it lies in SPACE(log² n). Another notable result, the Immerman-Szelepcsényi theorem, shows that NL = coNL: unlike what is conjectured for NP, the class is closed under complement. L ⊆ NL ⊆ P holds, and here too the strict inclusions remain open.
In short
- Space can be reused, which is why space classes behave differently from time classes.
- P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, with P ≠ EXPTIME.
- Savitch's theorem shows nondeterminism costs at most a square in space: PSPACE = NPSPACE.
- TQBF is PSPACE-complete, and many generalized games are too, owing to the same alternating structure.
- In logarithmic space, reachability is NL-complete and NL = coNL.
