Why does letting a memory-bounded machine guess its way through a search buy so much less than guessing appears to buy for time?
answer
- guessing is cheap to remove for memory
- reachability between two snapshots
- split the run at its midpoint
- depth times width: space squared
- polynomial squared is still polynomial
basics
~20 sSavitch's theorem removes the guessing at the cost of squaring the space: nondeterministic space s, for s at least logarithmic, is simulated deterministically in s squared. Squaring a polynomial is still a polynomial, so nondeterministic polynomial space equals polynomial space.
solid answer
~50 sFor memory, guessing is nearly free to eliminate. **Savitch's theorem** says that a nondeterministic machine using `s(n)` work cells, for `s(n)` at least logarithmic, can be simulated deterministically in `O(s(n)^2)` cells. The mechanism is a midpoint recursion: to ask whether configuration `b` follows configuration `a` within `t` steps, try every possible middle configuration `m` and ask the same question twice with budget `t/2`. Each level of the recursion stores only `a`, `b`, `m` and a counter — `O(s)` bits — and the depth is `log t`, which is `O(s)` because `t` is the configuration count `2^O(s)`. The consequence is that nondeterministic polynomial space collapses into **PSPACE**, since squaring a polynomial leaves a polynomial. For time there is no comparable collapse: the best general simulation costs an exponential blow-up, and whether a polynomial one exists is famously open.
code
pseudocode · 11 linesfunction CAN-REACH(a, b, t): // b reachable from a within t steps?
if t = 0: return a = b
if t = 1: return a = b or b is a legal successor of a
for each configuration m of width s: // one at a time, same cells reused
if CAN-REACH(a, m, t/2) and CAN-REACH(m, b, t/2):
return TRUE
return FALSE
// start with the full configuration count as the step budget
answer = CAN-REACH(start, accepting, 2^(c*s))
// depth = log(2^(c*s)) = c*s levels, each holding O(s) bitsgo deeper
Recall the headline only: for memory, a guessing machine can be replaced by an ordinary one at the cost of squaring the space, so nondeterministic polynomial space is just polynomial space.
Explain the mechanism. Reachability between two snapshots is split at a midpoint that is tried one candidate at a time; depth times per-level width gives the squared bound, and time explodes in exchange.
Be able to say why memory behaves so differently from time: cells are reusable and steps are not, which is the whole reason one resource absorbs guessing and the other does not.
Use it when judging a plan that depends on lucky search order. A design that fits a buffer only when it guesses right has a real deterministic version at roughly the squared buffer, but its cost moves entirely into repeated passes.
## The claim, stated precisely **Savitch's theorem:** for any space bound `s(n)` that is at least logarithmic, anything a nondeterministic machine decides using `s(n)` work cells, a deterministic machine decides using `O(s(n)^2)` work cells. Two substitutions make it concrete: - `s(n) = n^k` gives `n^(2k)`, still a polynomial. So **nondeterministic polynomial space and deterministic polynomial space are the same class**, and there is no separate "NPSPACE" worth naming. - `s(n) = log n` gives `log^2 n`. So nondeterministic logarithmic space is decidable in log-squared deterministic space. Note that this is *weaker* than what configuration counting already gives about time, and it does not close the gap between the two logarithmic classes. ## The question the recursion actually answers A nondeterministic run is a path through the machine's **configuration graph**: the nodes are the snapshots (state, both head positions, work tape contents), and there is an edge from one to another when a single nondeterministic step can go there. Acceptance means the accepting node is reachable from the start node. With `s` work cells there are `2^O(s)` nodes, so any path that exists has length at most `2^O(s)`. The naive deterministic method — walk the graph and remember which nodes you have seen — needs one bit per node, which is `2^O(s)` bits: catastrophic. The recursion avoids remembering anything. ## The midpoint trick, step by step 1. Define a predicate: *can b be reached from a in at most t steps?* 2. When `t` is 1 or 0, answer directly by checking whether `b` equals `a` or is a legal successor of `a`. This costs only the space to hold the two snapshots. 3. Otherwise, **enumerate every configuration m** of width `s`, one at a time, reusing the same cells for each candidate. 4. For each candidate ask the predicate twice, with budget `t/2`: from `a` to `m`, then from `m` to `b`. If both succeed, answer yes; if no candidate works, answer no. 5. Start the whole thing with `t` equal to the total configuration count, `2^O(s)`, since no longer path can exist without repeating. **Space accounting:** one level of recursion holds three snapshots and a counter, so `O(s)` bits. The depth is `log(2^O(s))`, which is `O(s)` levels. The product is `O(s^2)`. **Time accounting:** each level tries `2^O(s)` midpoints and each triggers two subcalls, so the running time is astronomically worse than the nondeterministic original. That is the whole trade — memory is reclaimed by redoing work instead of remembering it. ## Why time gets no such collapse The reason is the asymmetry between the two resources: - **Space is reusable.** The cells that held one midpoint attempt hold the next. Exploring an exponential number of possibilities costs nothing extra in memory as long as you explore them one at a time. - **Time is spent.** A step consumed cannot be reclaimed, so trying an exponential number of possibilities one at a time costs exponential time by definition. That single asymmetry is why the deterministic simulation of nondeterministic *space* costs only a squaring, while the deterministic simulation of nondeterministic *time* costs an exponential and nobody knows how to do better. | resource | can a deterministic machine absorb the guessing? | cost | |---|---|---| | space, at least logarithmic | yes, by Savitch's theorem | squared | | time | no known general method | exponential blow-up | ## A second surprise in the same direction There is a further result showing how differently space behaves. The **Immerman-Szelepcsenyi theorem** says that nondeterministic space, again from logarithmic upward, is closed under complement: if a guessing machine with `s` cells can confirm that something holds, another with `O(s)` cells can confirm that it does not. In particular nondeterministic logarithmic space equals its own complement class. The corresponding statement for nondeterministic *time* is not known and is widely doubted. Both results point the same way: memory bounds are far more forgiving of nondeterminism than time bounds are, which is exactly why the intuition "guessing must help enormously" is a time intuition misapplied. ## Reading it back at work For a tool crawling an enormous read-only archive through a fixed buffer, the moral is concrete. If you can describe a search that would fit in the buffer *provided you always guessed the right next hop*, then a real deterministic version fits in roughly the square of that buffer. What it will not do is finish anywhere near as fast — the deterministic version pays in passes what the guesser paid in luck.
- Why does the recursion enumerate midpoints instead of caching which configurations are reachable?Caching is what the theorem is avoiding. Marking reachable snapshots needs one bit per snapshot, and there are exponentially many in the space bound, so the table alone would dwarf the budget. Enumerating candidates reuses the same cells for each one, paying in repeated work rather than storage.
- Does the squaring result settle whether the two logarithmic-space classes are equal?No. It places nondeterministic logarithmic space inside deterministic log-squared space, which is a genuine improvement over the naive simulation but not a collapse to logarithmic space itself. Whether guessing helps at that exact bound belongs to the question of which inclusions in the chain are strict.
- What further result shows how differently memory treats nondeterminism?The Immerman-Szelepcsenyi theorem: nondeterministic space at or above logarithmic is closed under complement, so a guessing machine can confirm a negative answer within the same order of space. Nothing comparable is known for nondeterministic time, where the complement side is a separate open question.
Checking that a long journey is possible by asking about one halfway stop, then each half's halfway stop, needs only the current few place names in hand. You re-walk the route many times instead of remembering it.
saying these in an interview costs you the question
- Says the deterministic simulation costs nothing, ignoring the squaring
- Claims the same midpoint trick collapses nondeterministic time too
- Thinks the recursion stores the set of visited configurations
- Says the squaring proves the two logarithmic-space classes are equal
- Assumes the deterministic version also matches the guesser's running time