Savitch's theorem
/ SAV-itch /
Here is one of the genuine surprises of complexity theory. For time, we strongly suspect that letting a machine guess (nondeterminism) gives a huge, possibly exponential, boost: that is the P versus NP mystery. For space, guessing turns out to help only a little. Savitch's theorem (Walter Savitch, 1970) proves that nondeterministic space is at most quadratically more powerful than deterministic space, a tiny gap by complexity standards. Doubling the exponent on the space bound is the entire price of removing all the guessing.
Precisely, for any reasonable function f(n) at least log n, NSPACE(f(n)) is contained in SPACE(f(n)^2). The proof is a beautiful divide-and-conquer on the reachability question. To check whether configuration A can reach configuration B in at most 2^k steps, ask: is there a midpoint M such that A reaches M in at most 2^(k-1) steps AND M reaches B in at most 2^(k-1) steps? Recurse on each half, trying every possible midpoint M in turn. The recursion is only k = O(f(n)) levels deep, and each level stores one configuration (which takes O(f(n)) space), so the total work space is O(f(n)) times O(f(n)) = O(f(n)^2). The trade is stark: this deterministic simulation reuses space brilliantly but takes exponential time.
The headline consequence is PSPACE = NPSPACE: since the square of a polynomial is still a polynomial, deterministic and nondeterministic polynomial space coincide, so we never bother writing NPSPACE. Likewise NL is contained in SPACE((log n)^2). This is exactly the opposite of the time world, where we cannot collapse NP into P. The reason space can pull this off is reuse: the recursion overwrites the same cells at each level instead of needing fresh memory, something a time budget cannot mimic. Caveat: the price for erasing nondeterminism is paid in time, not space; the deterministic machine may run exponentially longer.
Applied to NL: directed reachability is in NL, and Savitch's recursion solves it deterministically in O((log n)^2) space. To ask 'does s reach t in <= n steps?', try every midpoint vertex m and recursively ask 's reaches m in <= n/2' and 'm reaches t in <= n/2'. The recursion is about log n deep, each level storing one O(log n)-bit vertex, giving O((log n)^2) total.
Savitch's midpoint recursion removes nondeterminism by squaring the space, at the cost of exponential time.
The quadratic space cost is paid back in time: the deterministic simulation can run exponentially longer than the nondeterministic original. Savitch trades time for space, not the reverse.