Savitch's theorem · the recursion tree

Savitch's theorem (1970) is the single most surprising result in space complexity: nondeterminism is essentially free in polynomial space. The space classes P and NP have a long-standing gap (we believe P ≠ NP), but the space classes PSPACE and NPSPACE are equal.

This is the inverse of what one would expect. For TIME, a single nondeterministic step can replace exponentially many deterministic steps (that is exactly the P vs NP question). For SPACE, a clever recursion can simulate any nondeterministic choice with only a quadratic blowup.

A nondeterministic Turing machine N using f(n) space has at most 2^O(f(n)) distinct configurations (state × tape contents × head position). So if N halts at all, it does so within that many steps.

The naive simulation — BFS over configurations — uses linear space in the number of reachable configurations, which is exponential. That breaks the bound. We need a smarter way.

Now we have a clean recursive question. The trick is to recurse cleverly.

Savitch's insight: cut t in half by guessing a midpoint configuration M.

Critically, the two recursive calls run in sequence, not in parallel, reusing the same memory. The for-loop also reuses memory: the M slot holds one config at a time.

Space O(f²), Time 2^O(f²). Wildly slow but space-efficient. The recursion tree below has exponentially many nodes, yet at any instant only a single root-to-leaf path sits on the stack.

Suppose N uses n bits of tape. Then:

• Number of configurations: 2^O(n).
• Maximum t: 2^O(n).
• Recursion depth: log t = O(n).
• Each stack frame stores one config: O(n) bits.
• Total deterministic space: O(n · n) = O(n²).

For n = 100: deterministic simulation uses roughly 10 000 bits of memory — but might run for 2^{10 000} steps. Space matters, time does not (for this theorem).

• PSPACE = NPSPACE · the immediate corollary.
• NL ⊆ L² · for f = log n, NSPACE(log n) ⊆ SPACE(log² n). This is the original tight application.
• TQBF · the canonical PSPACE-complete problem; Savitch's recursion is what lets us evaluate TQBF in polynomial space.
• Immerman–Szelepcsényi (1987/88) · NL = coNL. A different surprise; uses inductive counting, not midpoint recursion.
• Open question · is Savitch's f² tight? No improvement has been found in 55+ years.

1. "Just try every config." That uses exponential space (the list of seen configs). The midpoint trick is what avoids it.
2. "The tree has 2^{log t} leaves, so it uses that much space." No — the tree has that many leaves, but only one path lives on the stack at a time.
3. Confusing log t with t. log t = O(f), not O(2^f). Logs of exponentials are linear.
4. "Why doesn't this work for TIME?" Because both children must actually execute; their times add. log t × 2 child evaluations × loop over M = exponential time. Space, by contrast, gets reused.
5. Forgetting the floor of log t. If t is not a power of 2, round t/2 to ⌈t/2⌉ for the first half and ⌊t/2⌋ for the second. Doesn't affect asymptotics.

• Q1. Why doesn't Savitch's theorem prove P = NP?
  It only works for SPACE. The trick uses log t recursion depth — fine for space because each level reuses memory. But in TIME, we have to actually execute both children, so the running time multiplies and we get 2^{log t} = t total time. No speedup.
• Q2. Where does the f² come from?
  log t = log(2^O(f)) = O(f) recursion levels. Each level stores one configuration = O(f) bits. f levels × f bits = f² total.
• Q3. What's the midpoint M? How do we "guess" it?
  M ranges over all 2^O(f) possible configurations. We try them one by one in a deterministic loop. For each candidate M, recursively check both halves. If both succeed for some M, accept; if no M works, reject. The loop reuses the same M-slot in memory.
• Q4. Is Savitch's bound tight?
  Open question. We don't know if NSPACE(f) ⊆ SPACE(f^1.99) or even SPACE(f). Improving Savitch in any way is one of the great open questions of complexity theory.
• Q5. What problem in PSPACE actually motivates this?
  TQBF (true quantified Boolean formulas). Solving TQBF naïvely is exponential time. Savitch's idea applied directly: we can solve TQBF in PSPACE by alternating quantifier evaluation depth-first, reusing memory at each level.

Total time: 12 minutes.

• (2 min) Hook: "Nondeterminism is free in space — but not in time." Pose the contrast with P vs NP.
• (2 min) Define CANYIELD on the board. Argue: solving it solves the simulation problem.
• (3 min) Walk through the midpoint recursion. Stress the two key ideas: sequential calls, looping over M.
• (3 min) Run the visualization with depth 4 then depth 5. Pause when the explain panel mentions "only one root-to-leaf path on the stack".
• (2 min) Resource accounting: log t × O(f) bits = O(f²). Write it on the board.