Savitch's theorem

Statement

NSPACE(f(n)) ⊆ DSPACE(f(n)²) for space-constructible f(n) ≥ log n. Nondeterministic space is at most quadratically more powerful than deterministic space.

Formula

NSPACE(f(n)) ⊆ DSPACE(f(n)²)

Equation

NPSPACE = PSPACE

Proof sketch

Savitch showed that any nondeterministic Turing machine using space f(n) can be simulated by a deterministic one using space f(n)². The key is a recursive reachability algorithm that uses O(log n) space per level. Corollary: PSPACE = NPSPACE.