Introduction

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 Maze Without a Map

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">A maze is just a question: <b>is the exit reachable from the entrance?</b> The naive way walks the path and remembers every step. Savitch's way asks "can I reach a <b>midpoint</b>, then the rest?" — and barely remembers anything. Press <b>Solve</b> and compare the two memory counters.</p>
<div id="grid" class="grid"></div>
<div class="meters">
  <div class="meter"><span class="lbl">Path length (naive memory)</span><b id="pathLen">–</b></div>
  <div class="meter"><span class="lbl">Savitch peak memory (stacked midpoints)</span><b id="memUse">–</b></div>
</div>
<div class="status" id="status">Press Solve to search for a path.</div>
<div class="btns">
  <button id="solve" type="button">Solve (Savitch's way)</button>
  <button id="newmaze" type="button" class="ghost">New maze</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.grid { display: grid; gap: 2px; margin: .4rem 0; width: max-content; }
.c { width: 26px; height: 26px; border-radius: 4px; background: #e8eef3; }
.c.wall { background: #2b3a4a; }
.c.start { background: #1d3557; }
.c.goal { background: #0a7d33; }
.c.path { background: #ffd166; }
.c.start.path, .c.goal.path { box-shadow: inset 0 0 0 3px #ffd166; }
.meters { display: flex; gap: 1.2rem; flex-wrap: wrap; margin: .6rem 0; }
.meter { display: flex; flex-direction: column; }
.meter .lbl { font-size: .75rem; color: #667; }
.meter b { font-size: 1.4rem; color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Savitch's theorem, made visible. To decide if the goal is REACHABLE from the
// start, the naive method stores the whole path (memory ~ path length). Savitch
// instead asks reach(A,B,k): "is B reachable from A in <= k steps?" by trying
// every cell M as a MIDPOINT and recursing on reach(A,M,k/2) and reach(M,B,k/2).
// The recursion is only ~log2(k) deep, and each frame holds a constant number of
// cells, so PEAK MEMORY = number of stacked midpoints grows like log of the path
// length — never like the path itself. (Cheap in space, costly in time: faithful to Savitch, so the grid is kept small to stay snappy.)
const W = 7, H = 5;            // grid size (kept small: Savitch is time-expensive)
const K = 32;                  // step budget, a power of 2 >= longest path here
let grid, start, goal;
const idx = (r,c) => r * W + c;
const inB = (r,c) => r >= 0 && r < H && c >= 0 && c < W;

function neighbors(p){
  const r = (p/W|0), c = p % W, out = [];
  for (const [dr,dc] of [[-1,0],[1,0],[0,-1],[0,1]]){
    const nr = r+dr, nc = c+dc;
    if (inB(nr,nc) && grid[idx(nr,nc)] === 0) out.push(idx(nr,nc));
  }
  return out;
}

// Carve a maze that always has a start->goal path (random DFS spanning tree).
function build(){
  grid = new Array(W*H).fill(1);            // 1 = wall
  const st = [idx(0,0)]; grid[idx(0,0)] = 0;
  while (st.length){
    const p = st[st.length-1], r=(p/W|0), c=p%W;
    const opts = [];
    for (const [dr,dc] of [[-2,0],[2,0],[0,-2],[0,2]]){
      const nr=r+dr, nc=c+dc;
      if (inB(nr,nc) && grid[idx(nr,nc)] === 1) opts.push([nr,nc,r+dr/2,c+dc/2]);
    }
    if (!opts.length){ st.pop(); continue; }
    const [nr,nc,wr,wc] = opts[Math.random()*opts.length|0];
    grid[idx(wr,wc)] = 0; grid[idx(nr,nc)] = 0; st.push(idx(nr,nc));
  }
  start = idx(0,0); goal = idx(H-1, W-1);
  grid[goal] = 0;
}

// Savitch's recursive reachability. Returns a path (for drawing) but the real
// measure is PEAK RECURSION DEPTH = how many midpoints are stacked at once. Each
// live frame stores only a constant number of cells, so peak memory ~ that depth.
let peakMem = 0, depth = 0;
function reach(a, b, k){
  depth += 1;                                // one more stacked midpoint frame
  if (depth > peakMem) peakMem = depth;
  let res = null;
  if (a === b)               res = [a];
  else if (k === 1)          res = neighbors(a).includes(b) ? [a,b] : null;
  else {
    const half = Math.ceil(k/2);
    for (let m = 0; m < W*H && !res; m++){
      if (grid[m] === 1) continue;           // walls can't be a midpoint
      const left = reach(a, m, half);
      if (!left) continue;
      const right = reach(m, b, k - half);
      if (right) res = left.concat(right.slice(1));
    }
  }
  depth -= 1;
  return res;
}

function render(path){
  const g = document.getElementById('grid');
  g.style.gridTemplateColumns = `repeat(${W}, 26px)`;
  g.innerHTML = '';
  const onPath = new Set(path || []);
  for (let p = 0; p < W*H; p++){
    const d = document.createElement('div');
    let cls = 'c' + (grid[p] === 1 ? ' wall' : '');
    if (p === start) cls += ' start';
    if (p === goal) cls += ' goal';
    if (onPath.has(p)) cls += ' path';
    d.className = cls; g.appendChild(d);
  }
}
function setStatus(t, cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function newMaze(){
  build(); render(null);
  document.getElementById('pathLen').textContent = '–';
  document.getElementById('memUse').textContent = '–';
  setStatus('Press Solve to search for a path.', '');
}
function solve(){
  peakMem = 0; depth = 0;
  const path = reach(start, goal, K);         // budget K >= longest path here
  render(path);
  if (path){
    document.getElementById('pathLen').textContent = path.length;
    document.getElementById('memUse').textContent = peakMem;
    setStatus(fmt('Reached the exit. The path is %length% cells long, but Savitch never stacked more than %peakMem% midpoints — that is its tiny memory.', { length: path.length, peakMem: peakMem }), 'ok');
    console.log('path length =', path.length, '| Savitch peak depth =', peakMem);
  } else setStatus('No path exists in this maze.', 'bad');
}
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('newmaze').addEventListener('click', newMaze);
newMaze();


          

          

            Result
          

          
          

             Console
            
          

          

        

      

    


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.


The Real Complexity
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(f2f^{2}). A nondeterministic machine using memory f can be simulated by a deterministic machine using only f2f^{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\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 f2f^{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.


Where It Matters
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.


Conclusion
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.


Share this article
Pick a channel — or use your device's native share sheet.
 Comments 
Loading comments...
https://www.kipuhub.com/en/article/savitch/Content licensed under CC BY-NC 4.0.