The Hierarchy Theorems and the Class Map

What we already know, and the one thing still missing

Take stock of this rung. You learned to count memory with a separate read-only input tape so that a sublinear amount of work space even makes sense; you met L and NL, the problems solvable in logarithmic work space, and saw that graph reachability is the hardest problem in NL; you met PSPACE and its complete problems, the two-player games and quantified boolean formulas; and you watched two beautiful collapses — Savitch's theorem folding NPSPACE down into PSPACE, and Immerman–Szelepcsenyi showing NL equals co-NL. Every one of those results says 'this class is secretly the same as that one.'

So here is the unsettling realisation. We have a whole tower of named classes — L, NL, P, NP, PSPACE, EXPTIME — and so far nearly every theorem has shown two of them are equal or that we cannot tell them apart. We have never once proved that the tower is genuinely tall, that some higher class strictly contains a lower one. What if the whole thing quietly collapses to a single floor? This guide answers that fear. There is exactly one master technique that proves separation, it is an old friend in disguise, and it gives us the first rock-solid 'this is strictly bigger than that' in all of complexity theory.

Diagonalization, one more time

You have already seen this trick beat the halting problem: list the machines, build a new machine that deliberately disagrees with machine number i on input i, and you have manufactured something no machine on the list can be. That was Cantor's diagonal argument wearing a computer-science costume. The time hierarchy theorem is the very same move, but with a stopwatch bolted on. Instead of asking 'does machine i halt?', we ask 'does machine i halt within a generous time budget?' — and then disagree with the answer.

Fix a generous time budget, say f(n) steps, where f grows enough faster than g (the smaller budget we want to beat). Build a 'diagonal' decider D that reads an input which encodes some machine M plus that same encoding as M's input.
D simulates M on that input, but with a counter: it allows M only up to roughly g(n) steps — a careful universal simulation, the same idea as the universal Turing machine, costs only a modest extra factor that f(n) can absorb.
When the simulation finishes within budget, D outputs the OPPOSITE of what M did: if M accepts, D rejects, and vice versa. If M runs past its g(n) budget, D just halts and accepts (any fixed choice works).
Now suppose some machine running in g(n) time decided D's language. Feed that machine its own encoding. On that input D was built to do the exact opposite — a flat contradiction. So no g(n)-time machine computes D, yet D runs in f(n) time. The f(n) class is strictly bigger.

The payoff is immediate and concrete. Polynomial time and exponential time are far enough apart for the gap f-grows-faster-than-g to hold comfortably, so the time hierarchy theorem proves EXPTIME strictly contains P. That is real: P is not equal to EXPTIME, no asterisk, no open question. There genuinely exist problems that need exponential time and can never be squeezed into polynomial time. The exact same argument run on tape cells instead of clock ticks gives the space hierarchy theorem, so more space also strictly buys more power — for instance L is a strict subset of PSPACE.

Why the same trick cannot crack P versus NP

If diagonalization separates P from EXPTIME so cleanly, why not just point it at the famous P versus NP question and collect the prize? Here is the honest catch, and it is one of the deepest lessons in the field. Diagonalization works by simulating one machine inside another with only modest overhead. But that overhead, the universal-simulation cost, is exactly what stops it from telling P and NP apart: the gap between them, if there even is one, is too fine for a simulation-and-flip argument to resolve. P and NP are both 'polynomial-flavoured', and the diagonal trick needs a comfortable budget gap that a polynomial-versus-polynomial setting simply does not give.

Above NP: co-NP and the polynomial hierarchy

Before drawing the master map, two more landmarks sit between NP and PSPACE. Recall that a problem is in NP when a yes-answer has a short certificate you can check fast — a jigsaw that is hard to finish but easy to verify once someone hands you the solution. Now flip it: co-NP is the class where a no-answer has a short, checkable certificate. 'Is this formula satisfiable?' is in NP (show me a satisfying assignment); 'is this formula unsatisfiable, true for no assignment?' is the co-NP twin, and nobody knows a short certificate for that. Whether NP equals co-NP is open, and most believe they differ.

Stack those ideas and you get the polynomial hierarchy. NP problems can be phrased as 'does there exist a certificate such that a polynomial check passes?' — one 'there exists.' co-NP is 'for all guesses, the check passes' — one 'for all.' Allow alternating quantifiers — there-exists then for-all then there-exists, like a debate where each side answers the other — and each extra alternation defines a higher level of the hierarchy. It is the time-bounded echo of the quantifier-stacking you saw inside quantified boolean formulas for PSPACE, except the number of alternations stays a fixed constant rather than growing with the input.

The hierarchy is widely believed to be a genuine staircase, each level strictly above the last — but, honestly, that is conjecture. Worse (or more wonderfully), if it ever collapses, the collapse cascades: should P turn out to equal NP, the entire polynomial hierarchy would flatten down to P in one stroke. So this tower of quantifier-levels is bolted to the P-versus-NP question; pull that one pin and the whole structure could fall.

The whole map, and which doors are still locked

Now we can hang everything on one wall. Reading from frugal to lavish: L sits inside NL (more nondeterminism never hurts), NL sits inside P (Savitch and the reachability algorithm fit log-space work into polynomial time), P sits inside NP (a decider is a trivial verifier that ignores the certificate), NP sits inside PSPACE (you can recycle a polynomial amount of space to grind through exponentially many certificates one at a time), and PSPACE sits inside EXPTIME (a machine using polynomial space can only reach exponentially many distinct configurations before it must halt or loop). That chain is the complexity class map every student carries in their head.

  L  <=  NL  <=  P  <=  NP  <=  PSPACE  <=  EXPTIME
  |                                          |
  +----- ALL inclusions above are PROVED ----+
  +------- this END pair is PROVED STRICT ----+
         (NL strict in PSPACE; P strict in EXPTIME)

  PROVED to be NOT EQUAL (some gap is strict):
     NL  !=  PSPACE        (space hierarchy)
     P   !=  EXPTIME       (time hierarchy)

  STILL OPEN (could be equal, could be strict):
     L  vs  NL      NL vs  P      P vs  NP      NP vs PSPACE

  so: SOMEWHERE in L<=NL<=P<=NP<=PSPACE a strict gap must hide
      -- but we cannot yet point to WHICH link it is.

The class map at a glance. Every neighbour-to-neighbour inclusion is proved; the hierarchy theorems prove the two end-to-end gaps are strict, so at least one link in each chain must be strict — yet which one stays a mystery.

Stare at that map and feel the strange shape of our ignorance. The hierarchy theorems guarantee the chain L is-inside-NL-is-inside-P-is-inside-NP-is-inside-PSPACE cannot be all equalities, because its two endpoints, NL and PSPACE, are provably different — somewhere a strict gap is hiding. Yet we cannot finger a single one of those four links and prove it is the strict one. P versus NP is the most famous, but NL versus P and L versus NL are just as open. We have proved the staircase is not flat without being able to show which step is the tall one. That, more than any single theorem, is the honest state of the art — and it is exactly the cliff this whole ladder has been walking you toward.