Savitch Theorem and Time-Space Tradeoffs

Core Idea

Savitch's theorem proves PSPACE = NPSPACE: nondeterministic polynomial space equals deterministic polynomial space. Simulation requires squaring space (O(s²) for space s) but succeeds because space reusability bounds recursion depth. This contrasts sharply with time, where NP vs P remains open. Savitch highlights how time and space behave fundamentally differently in computational complexity.

Explainer

From your study of space complexity, you know that NSPACE(s(n)) is the class of languages decidable by a nondeterministic Turing machine using at most s(n) tape cells. The natural question is: how much additional space does a deterministic machine need to simulate a nondeterministic one? For time complexity, this question (P vs. NP) remains famously open. For space, Savitch's theorem gives a definitive answer: NSPACE(s(n)) ⊆ DSPACE(s(n)²) for any s(n) ≥ log n. The cost of removing nondeterminism is merely squaring the space bound.

The proof uses a clever recursive strategy called reachability testing. The core problem is: given a nondeterministic machine's configuration graph, can it get from the start configuration to an accepting configuration? Savitch's algorithm asks a simpler question recursively — "can configuration C₁ reach configuration C₂ in at most 2ᵏ steps?" — by guessing a midpoint configuration C_mid and checking both halves: can C₁ reach C_mid in 2^k-1 steps, and can C_mid reach C_mid in 2^k-1 steps? Each recursive call halves the step count, so the recursion depth is logarithmic in the number of steps. Since each stack frame stores one configuration (O(s(n)) space) and the recursion is O(s(n)) levels deep (because the total number of configurations is exponential in s(n)), the total space is O(s(n)²).

The key enabling property is that space can be reused but time cannot. When the algorithm finishes checking one midpoint, it reclaims that space and tries the next. A time-based simulation would need to preserve the history of all branches simultaneously, which is why the analogous result for time complexity remains elusive. This reusability is what makes space fundamentally different from time in complexity theory.

The most important consequence is that PSPACE = NPSPACE — nondeterminism gives no additional power for polynomial-space computation, since squaring a polynomial yields another polynomial. This collapses what could have been a vast gap into equality, and it stands in stark contrast to the time hierarchy where P vs. NP resists resolution. Savitch's theorem also explains why PSPACE-complete problems (like TQBF, the true quantified Boolean formula problem) are central to the complexity landscape: they capture the full power of polynomial space regardless of whether the machine is deterministic or nondeterministic.