Where we are: a tower of classes, mostly held together by faith
The last three guides built a vertical tower of resource classes. At the bottom sits NL, the problems a nondeterministic machine solves using only a logarithmic-size work tape beside its read-only input; its signature problem is reachability — can you get from node s to node t in a directed graph? Above NL come P, NP, then PSPACE (polynomial work-tape space, home of the quantified-formula and game-playing problems), and far overhead EXPTIME. The honest, slightly embarrassing truth is that almost every step in this tower is a one-way inclusion that nobody has proved is strict. We believe NL is smaller than P, and P smaller than NP, but we cannot prove it. This guide is about the rare places where the fog lifts — where we can say something surprising and certain.
For time, nondeterminism looks like a chasm: the whole P-versus-NP drama is the suspicion that a guessing machine can be exponentially faster than a plodding one. The shock of this rung is that for space, that chasm nearly closes. Two theorems — Savitch's and Immerman-Szelepcsenyi — show that letting a machine guess buys it almost nothing extra in memory. Memory, unlike time, can be reused: a step you take cannot be un-taken, but a tape cell you scribble on can be erased and written again. That single asymmetry is the secret engine behind every surprise here.
Savitch's theorem: guessing buys you almost no extra space
Here is the headline. Savitch's theorem says any nondeterministic machine using s(n) space can be simulated by a deterministic one using only s(n) squared space. Squaring sounds like a lot, but it is mild: the square of a polynomial is still a polynomial. The most quoted consequence is that PSPACE equals NPSPACE — nondeterministic polynomial space gives you nothing beyond deterministic polynomial space. Compare that to time, where converting a nondeterministic machine to a deterministic one costs an exponential blow-up that we have no idea how to avoid. For space, the price is merely a square.
How can this possibly be true? The trick is to recast the whole question as reachability — the same s-to-t problem that defines NL. A nondeterministic computation using space s explores a graph whose vertices are configurations (the machine's state plus its tape contents), and there are at most about 2^(s) of them. The machine accepts exactly when there is a path from the start configuration to an accepting one through this giant configuration graph. So "does this nondeterministic machine accept?" is literally "is the target reachable?" The deterministic simulator just needs to answer reachability frugally, reusing memory as it goes.
The frugal algorithm is a recursive divide-and-conquer with a beautiful idea at its core, sometimes called REACH or the middle-point method. To ask "can I get from a to b in at most k steps?", do not trace a path — instead guess the midpoint. There must be some configuration m halfway, so ask two smaller questions: can I reach m from a in k/2 steps, and m from b in k/2 steps? Try every possible m one at a time, reusing the same scratch space for each trial. The recursion is only about log(k) levels deep because k halves each time, and each level stores just one configuration of size s. Total space: log(k) times s. Since k is about 2^(s), log(k) is about s, and the grand total is s squared. That is the whole theorem, and the reuse of scratch space across the many trials of m is exactly the memory-recycling that time cannot do.
REACH(a, b, k): "can b be reached from a in <= k steps?"
if k == 1: return (a==b) OR (a -> b is one legal move)
for each possible midpoint configuration m: <-- reuse the SAME
if REACH(a, m, k/2) AND REACH(m, b, k/2): cell for each m
return YES
return NO
recursion depth ~ log(k) ~ log(2^s) = s levels
each level stores ~ s (one configuration)
TOTAL space ~ s * s = s^2 (NOT s^2 TIME -- time blows up!)Immerman-Szelepcsenyi: nondeterminism can count its own failures
The second surprise is about complementation — flipping yes and no. With a deterministic machine, complementing is trivial: run it and swap the answer. With a nondeterministic one it is not, and this is the same crux that makes co-NL (and co-NP) mysterious. A nondeterministic machine for reachability accepts when some path from s to t exists; it only needs one lucky branch to say yes. But to recognise the complement — to certify that t is unreachable — a single branch would have to somehow vouch that every path fails. That feels impossible for a guessing machine, and for decades people assumed NL and co-NL must differ.
They were wrong. The Immerman-Szelepcsenyi theorem proves NL equals co-NL: nondeterministic log-space classes are closed under complement. The technique that cracks it is called inductive counting, and the idea is gorgeous. Suppose the machine could compute the exact number of vertices reachable from s within i steps — call it count(i). Then it can verify the *un*reachable case: to certify that t is not reachable, nondeterministically guess and re-verify a reaching-path for each of the count(n) reachable vertices, confirm you found exactly that many, and check that t was not among them. If you can produce precisely the promised number of reachable vertices and t is missing, then t is genuinely unreachable — no path was overlooked, because the count itself is the proof of completeness.
And count(i) itself is built up step by step, layer by layer, computing count(i+1) from count(i) — each layer re-verified using only log space because, again, the scratch work is recycled rather than accumulated. The deep moral matches Savitch's: in the world of memory, a nondeterministic machine can be turned inside-out, because it can re-run and recount as often as it likes without paying in space. Honest scope: this closure under complement is a special blessing of space-bounded classes. Whether the analogous NP equals co-NP holds is wide open and widely doubted — the time world keeps its asymmetry.
The hierarchy theorems: a diagonal that finally proves something IS bigger
So far the surprises were collapses — classes turning out to be equal. But we also crave the opposite: a guarantee that more resource genuinely buys more power, that the tower is not secretly flat. The time hierarchy theorem and space hierarchy theorem deliver exactly that. Roughly: given meaningfully more time (or space), a machine can decide languages that no machine with meaningfully less time (or space) can. More really is more — for the same resource. These are among the few separations we can prove outright.
The proof is diagonalization — the same maneuver you watched defeat the halting problem and, before that, count the reals. Build a machine D with a generous time budget that does one cussed thing: simulate machine number i on input i, and then do the opposite of whatever that machine does within a smaller budget. Now D's behaviour disagrees with every small-budget machine on at least one input (the input naming that machine), so the language D decides cannot be decided by any of them. D needs only a little more time to run the simulation than the machines it out-argues — that overhead is why the gap must be more than a constant factor. The diagonal builds a witness to the strict separation by construction.
From this we harvest a clean, unconditional fact: P is not equal to EXPTIME. Exponential time strictly out-muscles polynomial time, no conjecture required — the time hierarchy guarantees a problem solvable in exponential time but provably not in any polynomial. It is worth savouring why this works when P-versus-NP does not. Diagonalization separates a class from a bigger version of the same resource (more time vs less time). It is helpless at separating different resources or different modes (deterministic time vs nondeterministic time) — there the two machines are not playing the same game, and the diagonal has no clean opposite to flip into. That blind spot is precisely why P-versus-NP resists this technique.
Reading the class map: what is settled, what is faith
Stack everything we have. The class map reads L inside NL inside P inside NP inside PSPACE inside EXPTIME, a single rising chain. This guide added landmarks within it: PSPACE equals NPSPACE (so adding nondeterminism to polynomial space is free, by Savitch), NL equals co-NL (Immerman-Szelepcsenyi), and at the deterministic side L sits inside NL sits inside P — itself a Savitch-flavoured fact since NL solved by the squaring trick lands inside polynomial time. Above NP, the polynomial hierarchy stacks alternating layers of "there exists" and "for all" — NP and co-NP being its first rung — and the whole tower nests snugly inside PSPACE.
Now the brutal honesty. Almost none of the neighbouring inclusions are known to be strict. We do not know whether L is smaller than NL, whether NL is smaller than P, whether P is smaller than NP, or whether NP is smaller than PSPACE. Every one of those is conjectured-yes and proved-nothing. The hierarchy theorems do hand us some strict gaps along the chain — most famously P is not equal to EXPTIME, and likewise NL is strictly inside PSPACE — which means at least one of the unproven links between them must be strict, we just cannot point to which. It is a genuinely strange state of knowledge: we have proved a fire exists somewhere in the building without being able to name a single burning room.