Space Complexity & Savitch's Theorem

Configuration counting, PSPACE versus NPSPACE, and Savitch's quadratic simulation.

The idea

Space complexity measures a Turing machine by the number of tape cells it uses: $\mathrm{SPACE}(f(n))$ collects the languages decided by deterministic machines in $O(f(n))$ space, $\mathrm{NSPACE}(f(n))$ is the nondeterministic analogue, and $\mathrm{PSPACE}$ and $\mathrm{NPSPACE}$ take all polynomial bounds.

Space differs from time in one decisive respect: it can be reused. A machine may run for exponentially many steps while touching only a few cells, so a space bound does not bound the running time. What it bounds is the number of distinct configurations — a state, a head position, and the tape contents. A machine confined to $s$ cells has only $2^{O(s)}$ configurations, and a computation is a path through that finite collection.

Theorem (Savitch's theorem).

For $f(n) \ge \log n$, every language decided by a nondeterministic machine using $f(n)$ space is decided by a deterministic machine using $O(f(n)^{2})$ space.

The deterministic machine does not follow the nondeterministic one step by step. Acceptance asks whether the start configuration reaches an accepting one, but storing such a path would need far too much room. Instead, decide whether $c_1$ reaches $c_2$ within $t$ steps by trying each possible midpoint configuration $c_m$ and recursing on the two halves, each with budget $t/2$. Each level of recursion holds one configuration, and repeatedly halving the budget leaves only $O(f(n))$ levels, so the space multiplies by the depth rather than accumulating along the path. The simulation costs enormous time, but its space is only a square.

Corollary.

$\mathrm{PSPACE} = \mathrm{NPSPACE}$.

The square of a polynomial is a polynomial, so the simulation keeps every nondeterministic polynomial-space language inside $\mathrm{PSPACE}$.

Ways to work on it

• Walkthrough. Count configurations of a space-bounded machine and trace Savitch's recursive reachability search.
• Practice. Apply Savitch's quadratic blow-up to a concrete space bound.
• Hardest. Derive the polynomial space bound of Savitch's simulation.

Not sure where to start? Take the ten-question placement test.