Savitch's Theorem

A nondeterministic Turing machine $N$ using space $f(n)$ has, for each input of length $n$, a configuration graph $G_N$: vertices are configurations (tape contents, head positions, state — everything needed to resume computation), and there is a directed edge $C_1 \to C_2$ if $N$ can move from $C_1$ to $C_2$ in one step. Because $N$ uses only $f(n)$ space, the number of configurations is bounded by

for some constant $c$ depending on the machine's alphabet and state set — exponential in $f(n)$, but each individual configuration can be written down using only $O(f(n))$ bits. $N$ accepts its input if and only if there is a directed path in $G_N$ from the start configuration $C_{\text{start}}$ to some accepting configuration $C_{\text{accept}}$. This reduces the language-membership question to a graph reachability question on an exponentially large but implicitly-described graph. The brute-force way to decide reachability — breadth-first or depth-first search, storing a visited-set — would need to remember which of the exponentially many configurations have been seen, costing exponential space. Savitch's trick avoids ever storing the visited set. The key auxiliary notion is yieldability with a step bound: define $\text{REACH}(C_1, C_2, t)$ to be true iff $N$ can get from $C_1$ to $C_2$ in at most $t$ steps. Because the whole graph has at most $c^{f(n)}$ vertices, if a path exists at all, one exists using at most $c^{f(n)}$ steps (no need to revisit a vertex). So acceptance is equivalent to $\text{REACH}(C_{\text{start}}, C_{\text{accept}}, c^{f(n)})$. The magic step is realizing that $\text{REACH}(C_1, C_2, t)$ can be answered by guessing a midpoint configuration $C_m$ and recursively checking $\text{REACH}(C_1, C_m, t/2)$ and $\text{REACH}(C_m, C_2, t/2)$ — cutting the time parameter in half while only adding one configuration (size $O(f(n))$) to the recursion stack.

The algorithm is a recursive procedure `CANYIELD(C1, C2, t)` that returns true iff $C_1$ can reach $C_2$ in at most $t$ steps of $N$. The top-level call uses $t = c^{f(n)}$, the maximum meaningful number of steps (larger than the total configuration count would ever require). ``` // N: a nondeterministic TM using space f(n) // C1, C2: configurations of N (encoded in O(f(n)) bits) // t: a step budget (a power of two, WLOG, for clean halving) function CANYIELD(C1, C2, t): if t == 1: return (C1 == C2) or (N can move from C1 to C2 in exactly one step) // base case checked directly: O(f(n)) space, no recursion if t > 1: for every configuration Cm of N that uses <= f(n) space: // Cm ranges over all c^{f(n)} possible configurations, // trying them one at a time and REUSING space each time if CANYIELD(C1, Cm, ceil(t/2)) and CANYIELD(Cm, C2, floor(t/2)): return true return false function DETERMINISTIC-SIMULATE(N, x): n = length(x) C_start = initial configuration of N on x // try every accepting configuration reachable within max steps T = c^(f(n)) // upper bound on path length in G_N for every accepting configuration C_accept: if CANYIELD(C_start, C_accept, T): accept reject ``` The crucial implementation detail — the one that makes the space bound work — is how the `for every configuration Cm` loop and the recursive calls share memory. At each level of recursion we only need to store:

• the current pair $(C_1, C_2)$ being tested, each $O(f(n))$ bits,
• the current candidate midpoint $C_m$ being tried, $O(f(n))$ bits,
• the current step budget $t$ (or equivalently the recursion depth, a number up to $\log T = O(f(n))$, needing $O(\log f(n))$ bits to store as a counter),

and then the recursive call to `CANYIELD` for the left half can reuse this same block of memory, and once it returns, the same memory is reused again for the right half. This is exactly like how depth-first recursion on a tree only needs to store one root-to-current-node path at a time, not the whole tree.

The final algorithm calls `CANYIELD(C_start, C_accept, T)` for each of the finitely many accepting configurations (or, equivalently, adds a single "super-accept" configuration reachable from all accepting ones), and accepts iff any call returns true.

Space bound. Let $f(n) \ge \log n$ be space-constructible, and suppose $N$ is a nondeterministic TM deciding a language in space $f(n)$. The configuration graph has at most $T = 2^{O(f(n))}$ vertices (a standard counting bound: states × head positions × tape contents over $f(n)$ cells), so we may take $T = 2^{k \cdot f(n)}$ for a constant $k$. The recursion `CANYIELD(C1, C2, t)` has depth exactly $\lceil \log_2 t \rceil$, since $t$ halves at each level down to the base case $t = 1$. With $t = T = 2^{k f(n)}$, the depth is

At each level of the recursion, the algorithm must store the current pair of configurations $(C_1, C_2)$ (or $(C_1, C_m)$, etc.), each requiring $O(f(n))$ bits, plus $O(\log f(n))$ bits to track which candidate midpoint is currently being tried (an index into $2^{O(f(n))}$ candidates still only needs $O(f(n))$ bits to write down explicitly, since we store the actual configuration, not an abstract index) and $O(\log \log T) = O(\log f(n))$ bits for a loop counter. So each stack frame costs $O(f(n))$ space, and there are $O(f(n))$ frames alive simultaneously (one per recursion level, since it's depth-first), giving total space

This proves $\text{NSPACE}(f(n)) \subseteq \text{SPACE}(f(n)^2)$.

Why reuse works (the key invariant). The crucial invariant is: at any moment during execution, the deterministic simulator's memory holds exactly one root-to-current-node path in the recursion tree, never two siblings at once. This is guaranteed because the algorithm is depth-first: it fully completes (and discards) the left recursive call `CANYIELD(C1, Cm, t/2)` before beginning the right one `CANYIELD(Cm, C2, t/2)`, reusing the exact same tape region for both. Because the recursion tree has depth $O(f(n))$ and each level's frame is $O(f(n))$ bits, no matter how astronomically wide the tree is (branching factor up to $2^{O(f(n))}$ at each level, since we try every possible midpoint), the space used is proportional only to the tree's depth, not its size. This is the whole trick, and it is why space complexity behaves so differently from time complexity: a time-bounded algorithm cannot "forget" the branches it explored (it must sequentially spend time on each), but a space-bounded algorithm can throw away all information about a branch as soon as it's done with it.

Correctness (proof sketch by induction on $t$). Claim: `CANYIELD(C1, C2, t)` returns true iff $N$ can reach $C_2$ from $C_1$ in at most $t$ steps.

• Base case $t = 1$: trivially correct — either $C_1 = C_2$ (zero steps) or there's a direct one-step transition, which is checked exhaustively from $N$'s transition function.
• Inductive step: Suppose the claim holds for all budgets less than $t$. If $C_1 \to^{\le t} C_2$ via some path of length $\le t$, let $C_m$ be the configuration at the midpoint of that path (position $\lceil \text{len}/2 \rceil$). Then $C_1 \to^{\le \lceil t/2\rceil} C_m$ and $C_m \to^{\le \lfloor t/2\rfloor} C_2$, so by the inductive hypothesis both recursive calls with budget halved return true for this choice of $C_m$ — and the algorithm tries every possible $C_m$, so it will find this one. Conversely, if the algorithm returns true for some $C_m$, then by the inductive hypothesis both halves are genuine sub-paths, which concatenate to a path of length $\le t$ from $C_1$ to $C_2$. $\blacksquare$

Time cost (the honest tradeoff). Savitch's construction is not time-efficient. The recursion at each level branches over all $2^{O(f(n))}$ possible midpoints, and there are $O(f(n))$ levels, giving a time bound of roughly

which is far worse than the original nondeterministic running time. Savitch's Theorem is purely a space result; it says nothing good about time, and indeed no polynomial-time simulation of NSPACE by DSPACE machines is known — that would collapse major complexity classes. This tradeoff — quadratic space blowup at the cost of a much larger time blowup — is the price of removing nondeterminism this way, and it is the honest limitation of the technique.

Corollary — PSPACE = NPSPACE. If $L \in \text{NSPACE}(n^k)$ for some polynomial bound, Savitch's theorem places $L$ in $\text{SPACE}((n^k)^2) = \text{SPACE}(n^{2k})$, still a polynomial. Hence nondeterministic polynomial space equals deterministic polynomial space:

This is a genuinely different phenomenon from $\text{P}$ vs. $\text{NP}$: while allowing nondeterminism is conjectured to give strictly more computational power in polynomial time, it provably gives no extra power at all in polynomial space.

Consider a tiny nondeterministic machine $N$ whose configuration graph on some fixed input is the following 6-vertex directed graph (imagine configurations labeled by tape snapshots, abbreviated $A$–$F$):

Let $C_{\text{start}} = A$ and $C_{\text{accept}} = F$. There are $|V| = 6$ configurations, so any existing path has length at most $6$; round up to $T = 8$ (a power of two) as the step budget for the top-level call. We trace `CANYIELD(A, F, 8)`. The algorithm tries every candidate midpoint $C_m \in \{A,B,C,D,E,F\}$ in some fixed order, recursing with budget $4$ on each half, until one succeeds.

(The $C_m = A$ branch is explored first in a real run but shown here abbreviated; the important content is the successful branch.) Once $C_m = B$ is tried, `CANYIELD(A,B,4)` recurses: try midpoints for the $A\to B$ sub-problem; $C_m = B$ itself works immediately since `CANYIELD(A,B,2)` further reduces to the direct-edge base case. Similarly `CANYIELD(B,F,4)` succeeds via midpoint $C_m = D$: `CANYIELD(B,D,2)` is a direct edge (true), `CANYIELD(D,F,2)` is a direct edge (true). Both recursive calls bottom out at $t=1$ direct-transition checks, which read straight from $N$'s transition table. So `CANYIELD(A,F,8)` returns true, correctly reflecting that $A \to B \to D \to F$ is a genuine accepting path of length 3.

Space accounting for this trace. At the deepest point of the successful path, the recursion stack holds frames for budgets $8, 4, 2, 1$ — depth $\log_2 8 = 3$ plus the base case, i.e. $4$ live frames, each storing a pair of configuration labels (a few bits each, since only 6 configurations exist). If instead $N$ used $f(n) = 20$ bits per configuration and had a configuration graph of size $2^{20}$, the analogous trace would have recursion depth $\log_2(2^{20}) = 20$ levels, each holding $O(20)$ bits — total $O(20 \times 20) = O(400) = O(f(n)^2)$ bits, exactly matching the general bound derived above.

Savitch's Theorem is not merely a historical curiosity; it is a load-bearing result in the architecture of complexity theory. It directly establishes that PSPACE = NPSPACE, which means that whenever a system's resource bound of interest is polynomial space — as in analyzing board games, planning problems, or verification tasks with large but boundable state spaces — nondeterminism (the ability to guess a winning strategy or a satisfying assignment) provides no theoretical advantage in the space required, even though it may dramatically help in time. This underlies why problems like generalized geography, quantified Boolean formula satisfiability (TQBF), and many two-player game analyses are studied inside PSPACE without needing to separately track a nondeterministic variant. The same reachability-doubling idea, applied at the sub-polynomial scale, shows $\text{NL} \subseteq \text{SPACE}(\log^2 n)$: any problem solvable nondeterministically with logarithmic memory — including graph reachability itself (directed s-t connectivity), a core primitive behind compilers' dataflow analyses, dependency resolution, and network routing reachability checks — can be solved deterministically using only $O(\log^2 n)$ memory. (The Immerman–Szelepcsényi theorem later sharpened understanding of $\text{NL}$ further, showing it is closed under complement, but Savitch's quadratic bound remains the classical general-purpose tool for taming nondeterminism in space.) Beyond its direct corollaries, the reachability method itself — recursively splitting a path-existence question at a guessed midpoint — became a reusable proof technique across theoretical computer science, appearing in space-bounded simulation arguments, in the proof that TQBF is PSPACE-complete, and in the general study of how memory, unlike time, can be recycled. Any system or algorithm that reasons about implicitly-described exponential state spaces using only polynomial working memory — model checkers, symbolic planners, certain automated theorem provers — rests conceptually on the same insight Savitch formalized: space is a renewable resource.

Ask the tutor: Can you walk through why the recursion depth in CANYIELD is logarithmic in the number of configurations, and how that directly produces the f(n)² space bound?