Savitch's Theorem
You'll learn: How nondeterministic space can be simulated deterministically with only a quadratic increase in space.
The Core Insight
In our exploration of complexity classes, we've seen that PSPACE contains problems solvable with polynomial space. But what about nondeterministic space? Could a machine that "guesses" correctly use dramatically less space than one that must try everything systematically?
Savitch's Theorem answers this with surprising optimism: nondeterminism only gives you a quadratic advantage in space.
Specifically, if a nondeterministic Turing machine can solve a problem using f(n) space, a deterministic machine can solve it using at most f(n)² space.
Why This Matters
Think of searching through a maze. A nondeterministic machine can "magically guess" the right path, keeping track of just the current location (minimal space). A deterministic machine must systematically explore, but Savitch showed you don't need to store the entire exploration tree—just cleverly divide and conquer.
The key trick: to check if you can get from configuration A to configuration B in t steps using s space, recursively check if there's a midpoint configuration C reachable from A in t/2 steps and from which B is reachable in t/2 steps. Reuse the space for each recursive call!
Practical Impact
This theorem proves that NSPACE(f(n)) ⊆ DSPACE(f(n)²), where NSPACE is nondeterministic space and DSPACE is deterministic space. As a corollary, PSPACE = NPSPACE—polynomial nondeterministic space equals polynomial deterministic space.
Key Takeaway: Savitch's Theorem shows that nondeterministic space is surprisingly tame—it can always be simulated deterministically with only quadratic space overhead, making space complexity more "robust" than time complexity.