Space Complexity and the Hierarchy Theorems

When we sorted problems into P, NP and PSPACE, we mostly measured algorithms by time — how many steps they take. But there is a second, equally fundamental resource: space, the amount of memory a computation needs at once. This page is about measuring by memory, and about the surprising ways space behaves differently from time.

Here is the key intuition that makes space its own story: memory is reusable, but time is not. Once a second has ticked past you can never get it back — but a memory cell can be erased and written again a billion times. So a machine that is careful never to hold more than a little scratch paper at once can still run for an enormous number of steps. Space is the thriftier resource, and that single fact ripples out into some of the most beautiful theorems in the whole theory of computation.

Measuring memory: L, NL and PSPACE

Space complexity counts the number of memory cells a Turing machine uses on its work tape — the read-only input doesn't count, so we can honestly talk about machines that use less memory than the size of the input. That gives us a ladder of classes:

L ("logspace") — solvable using only O(\log n) memory. That is astonishingly little: enough to hold a handful of pointers or counters into the input, but nowhere near enough to copy the input itself.
NL ("nondeterministic logspace") — the same tiny memory budget, but the machine is allowed lucky guesses, exactly as NP is the lucky-guess version of P.
PSPACE — solvable with a polynomial amount of memory, O(n^k), and no limit at all on time.

And just as before, these nest neatly, with the time classes threaded in between:

\mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}

The landscape, nested

Every containment below is a proven theorem. Reveal the classes from the inside out — from the thriftiest (logspace) to the roomiest — and watch how each one sits inside the next.

A logspace example worth carrying in your head lives in NL: graph reachability — "is there a path from vertex s to vertex t?" A nondeterministic machine can solve it while remembering only the vertex it is currently standing on (that is just O(\log n) bits — enough to name one vertex), repeatedly guessing which edge to follow next. It never has to store the whole path, so its memory stays tiny even though the graph is huge.

Why polynomial space can afford exponential time

Suppose a machine explores a game tree — say, "does the first player have a forced win?" There might be an exponential number of positions to examine. A time-bounded machine would be sunk. But a space-bounded machine can walk the tree depth-first, remembering only the single line of play it is currently on — reusing those same cells the instant it backtracks.

The current line is at most n moves deep, so the memory needed is only polynomial — even though the machine visits exponentially many positions over time. This is the whole reason PSPACE is so roomy: you pay for the deepest branch, not the total number of branches. Reusing memory is the free lunch that time can never offer.

O(\log n) space sounds almost too stingy to be useful — but a logarithm is exactly the number of bits you need to write down one index into an input of size n. A million-vertex graph needs only about 20 bits to name any single vertex. So a logspace machine can hold "a few pointers and counters" — which, cleverly used, is enough to check connectivity, do arithmetic, and recognise a whole family of languages, all without ever copying the input it is reading.

Savitch's theorem: nondeterminism barely helps for space

Now the punchline. For time, the gap between deterministic and nondeterministic — the \mathrm{P} versus \mathrm{NP} question — is the most famous open problem in the field, and everyone believes the gap is enormous. For space, the answer is known, and it is almost nothing:

Any problem solvable by a nondeterministic machine in space s(n) can be solved by a deterministic machine in space s(n)^2: \mathrm{NSPACE}(s) \subseteq \mathrm{DSPACE}(s^2).
Squaring a polynomial gives another polynomial, so the whole class collapses: \mathrm{PSPACE} = \mathrm{NPSPACE}. Allowing lucky guesses buys you no new problems at all when you are counting memory.
The proof is a gem: to decide whether a machine can get from configuration A to configuration B in 2^k steps, guess a midpoint M and recursively check A \to M and M \to B in half the time each — reusing the same memory for both halves. That recursion is only O(\log) deep, so the space just squares.

Savitch's midpoint trick is really the same idea as the depth-first game-tree walk: trade time for space by reusing memory across sub-problems. It is why nondeterminism, which is world-changing for time, is a shrug for space.

\mathrm{PSPACE} = \mathrm{NPSPACE} does NOT mean \mathrm{P} = \mathrm{NP}. It is tempting to reason: "we proved deterministic equals nondeterministic for space, so surely the same holds for time." No. Savitch's trick works precisely because memory can be reused — the two recursive halves share the same cells. Time cannot be reused: the steps spent on the first half are gone before the second half begins, so squaring the resource would mean squaring the running time, which is a genuine blow-up, not a collapse. Space and time behave differently, and the open \mathrm{P} vs \mathrm{NP} question is living proof that the space result does not carry over.

The hierarchy theorems: more resource, strictly more power

One more deep fact ties the whole picture together. It would be a disaster for the theory if giving a machine more memory (or more time) let it solve exactly the same problems — the classes would all be secretly equal and the ladder would collapse. The hierarchy theorems guarantee this does not happen: more of a resource genuinely lets you solve strictly more problems.

Space hierarchy: if f grows genuinely faster than g, then \mathrm{DSPACE}(g) \subsetneq \mathrm{DSPACE}(f) — a strict inclusion. There are problems solvable with n^2 memory that are impossible with only n.
Time hierarchy: likewise, more time buys strictly more power, e.g. \mathrm{DTIME}(n^2) \subsetneq \mathrm{DTIME}(n^3) (up to a log factor).
A headline consequence: \mathrm{P} \subsetneq \mathrm{EXPTIME} is proven. Exponential time really can do things polynomial time cannot — so somewhere in the long chain \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}, at least one \subseteq must be a strict \subsetneq — we just don't know which.

These are among the few things we can prove separate two classes — a rare victory, since so much of complexity theory is a museum of open problems.

The bound has to be constructible — space-constructible (or time-constructible), meaning a machine can actually compute the value f(n) from n within that very budget. This rules out pathological, uncomputable "bounds." For every function you would ever meet — \log n, n, n^2, 2^n — the condition holds, so in practice the hierarchy theorems say exactly what you'd hope: a bit more room, a bit more power. But the fine print matters: without constructibility, there are strange gaps where extra resource buys nothing (the gap theorem), so the hypothesis is not just decoration.

The big contrast, in one line

Keep this pairing in your pocket — it is the soul of this whole page:

For space, we know deterministic equals nondeterministic: \mathrm{PSPACE} = \mathrm{NPSPACE} (Savitch).
For time, the analogous question — \mathrm{P} \overset{?}{=} \mathrm{NP} — is famously open, and believed to be a resounding "no".

Same question, two resources, two utterly different answers — all because memory can be reused and a second, once spent, cannot.