P35 · PSPACE = NPSPACE

🔊 Listen

1 · Savitch's theorem · the canonical NSPACE collapse

Savitch's theorem (Sipser §8.2): for f(n) ≥ log n, NSPACE(f(n)) ⊆ SPACE(f²(n)). The polynomial blowup is only quadratic, so PSPACE = NPSPACE — nondeterminism gives no extra power in polynomial space. (Contrast with P vs NP, which is open.)

The CANYIELD reduction

For an NSPACE(f) machine on input w, "does it accept?" is equivalent to "is there a path in the configuration graph from C_start to some C_accept in ≤ 2^O(f) steps?"

Define CANYIELD(c, d, t) = true iff c reaches d in ≤ t steps. Recursive structure:

CANYIELD(c, d, t):
  if t = 1: check (c, d) is an edge
  else: for each midpoint m:
    if CANYIELD(c, m, t/2) and CANYIELD(m, d, t/2): return true
  return false

The recursion has log₂(t) = O(f) levels. Each level stores one configuration (size O(f)) on the stack. Total space: O(f) levels × O(f) per frame = O(f²). Quadratic, not exponential — that's the magic.

Crucial: space can be reused

Each recursive call reuses the same f² cells when the previous call returns. Time can't be reused this way, which is why no analogous "NTIME(f) ⊆ TIME(f²)" result exists.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

f² is the upper bound, not the lower. Whether NSPACE(f) ⊊ SPACE(f) is open. The quadratic blowup is what we can prove; it might be unnecessary.
Recursion depth is log(t), not log(f). Time budget t = 2^O(f), so log(t) = O(f). That's the depth count.
"CANYIELD" exists in the proof, not in the algorithm. It's a thought-experiment routine. The actual implementation reconstructs configs by their O(f)-bit encodings.

🔊 Listen

4 · Q&A defence notes

Q1. Why f² and not just f?
Recursion depth = log(t) = O(f) levels. Each frame stores one configuration (size O(f)). Total stack size = O(f) levels × O(f) per frame = O(f²).
Q2. Why doesn't this trick work in TIME?
Time can't be reused. In space, when a recursive call returns, the cells are free for the next call. In time, even if you computed something earlier, you still spent the time on it. CANYIELD's two recursive calls would take t/2 + t/2 = t time — no savings.
Q3. So is NTIME(f) ⊆ TIME(f²) similarly?
No — that's exactly the P vs NP question (or close to it). NTIME(n^k) ⊆ TIME(n^poly) would imply P = NP. Savitch's technique fundamentally relies on space reusability.
Q4. Does Savitch give an efficient algorithm?
In theory yes; in practice no. The constant-factor overhead is brutal and CANYIELD's recursion explores all possible midpoints. The theorem is conceptually crucial but not practically used.

🔊 Listen

5 · Where to read more

Sipser: Theorem 8.5 (Savitch). Lecture notes: Module 6 slide 1. Companion problems: P34 (Savitch tree), P33 (space-time chart).