Savitch's Theorem

Imagine standing at the entrance of a huge maze and being granted one magical power: at every fork you always guess the correct turn. With that gift you reach the exit in a single, perfect walk. This is nondeterminism — the idea that a machine can effortlessly pick the right path among exponentially many.

For time, this power looks enormous: it is exactly what separates the easy class P from the famously hard NP. But here is a stranger question. What if we don't count how long the journey takes, but how much memory we need to carry along the way — a notepad to remember where we are?

Savitch's theorem gives a beautiful, almost paradoxical answer. When you measure memory instead of time, guessing is nearly worthless. A machine that guesses its way through can be simulated by an ordinary, deterministic one using only a little more memory — the square of what the guesser used. That single fact reshapes how we think about the limits of computation.

The heart of Savitch's proof is a single, clever question about a maze: is the exit reachable from the entrance? The lazy way is to walk the path and remember every step — but that notepad can grow as long as the path itself. Savitch's trick remembers almost nothing.

Instead of storing a route, it asks a recursive question: "Can I get from A to B in at most k steps?" To answer it, the algorithm tries every cell M as a possible midpoint, and asks two smaller questions — can I reach M from A in k/2 steps? and can I reach B from M in k/2 steps? Each halving needs only enough memory to hold one cell, and the recursion is only about log(steps) deep.

<p class="hint">{{hint_text}}</p>
<div id="grid" class="grid"></div>
<div class="meters">
  <div class="meter"><span class="lbl">{{lbl_path_len}}</span><b id="pathLen">–</b></div>
  <div class="meter"><span class="lbl">{{lbl_mem_use}}</span><b id="memUse">–</b></div>
</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="newmaze" type="button" class="ghost">{{btn_new_maze}}</button>
</div>

// Code not found

// Code not found

Press Solve and watch the counters. The grid may have hundreds of cells and the path may wind across all of them, yet the peak memory stays astonishingly small — it grows like the square of the logarithm of the maze size, never like the path length. That gap between "remember the whole route" and "remember one midpoint at a time" is Savitch's theorem made visible.

So what exactly did Savitch prove, and how strong is the claim?

• The statement. For any reasonable function f(n) ≥ log n, NSPACE(f) ⊆ DSPACE($f^{2}$). A nondeterministic machine using memory f can be simulated by a deterministic machine using only $f^{2}$ memory. This is a proven theorem — Walter Savitch, 1970 — not a conjecture and not an open question.
• The big corollary. Apply it with f = polynomial and the square is still polynomial, so PSPACE = NPSPACE: for polynomial memory, nondeterminism adds nothing at all. Apply it with f = log n and you get NL ⊆ DSPACE($\log ^{2}$ n).
• The engine is the recursive midpoint trick from the demo, applied to the configuration graph of the machine — the (exponentially many) snapshots of its memory. Reachability in that graph means "the machine can accept," and the halving recursion solves it in space $f^{2}$ without ever listing the graph.
• The sharp contrast with time. For time, the analogous question — does P equal NP? — is the most famous open problem in the field. Savitch shows the space story is completely different: guessing saves time spectacularly but saves memory hardly at all.

One honest caveat: the square is the best simulation we know, but whether it is truly necessary is still open (this is the NL vs L question, tied to P vs NP-style barriers). What is settled is the upper bound — and that alone collapses an entire class.

Savitch's theorem is not just a curiosity about Turing machines — it underpins how we reason about systems whose state space is astronomically large but whose memory budget is tiny.

• Model checking and verification. Asking "can this protocol ever reach a bad state?" is graph reachability over an exponential configuration space. Savitch-style search lets tools explore it in modest memory instead of storing every reachable state.
• Games and planning. Deciding the winner of many two-player games is PSPACE-complete. Because PSPACE = NPSPACE, designers know that "just let the machine guess the winning line" buys no extra power for memory — a result that shapes the whole landscape of QBF and PSPACE.
• Memory-bounded algorithms. The same divide-and-conquer-on-the-midpoint idea inspires real space-efficient algorithms when storing the full answer is impossible.
• Drawing the map of complexity. PSPACE = NPSPACE is one of the few clean collapses we can prove, and it anchors the whole hierarchy of space classes.

In short, Savitch tells engineers something practical: when the bottleneck is memory rather than time, the brute force of guessing barely helps, so cleverness has to come from elsewhere.

Nondeterminism is one of computer science's most seductive ideas: a machine that always guesses right. For time, that gift is so powerful we still can't fully measure it — it is the gap at the heart of P vs NP. For memory, Savitch settled the matter in 1970: the gift is nearly worthless. Simulating the guesser deterministically costs only a squaring of the space, and so PSPACE = NPSPACE.

The maze with no map is the perfect picture of why. You never need to remember the whole winning path; you only ever need to remember one midpoint at a time. That is the difference between a notepad as long as the journey and one barely longer than its logarithm — and it is the reason a lucky guess, so precious when you are racing the clock, is almost free to do without when you are short on memory.