The Time Hierarchy Theorem

Common sense says a computer with more time should solve strictly more problems than one with less. Remarkably, in complexity theory very few "obvious" separations can actually be proven — \mathrm{P} versus \mathrm{NP} has resisted for half a century. The time hierarchy theorem is one of the precious exceptions: it makes the intuition rigorous. Give a Turing machine asymptotically more time and it can decide languages that no faster machine can decide at all. More time is not just convenient — it is genuinely more powerful.

This is the theorem that keeps complexity theory from being vacuous. Without it, we could not rule out the nightmare that \mathrm{L} = \mathrm{P} = \mathrm{NP} = \mathrm{PSPACE} = \mathrm{EXP} — one giant class in a trench-coat. The hierarchy theorem plants a firm flag: at least some of those classes really are different.

The statement

Informally: for time bounds that are "well-behaved", a modestly larger budget strictly enlarges what you can decide. The precise version is:

If f(n) is a time-constructible function, then

\mathrm{DTIME}\!\big(o(f(n))\big) \;\subsetneq\; \mathrm{DTIME}\!\big(f(n)\log f(n)\big).

That is: there is a language decidable in time f(n)\log f(n) that is not decidable in time o(f(n)) by any machine at all.

The \log f factor is the price of the simulation used in the proof, and on a multi-tape model it can be shaved to a constant; the moral is unchanged. The clean takeaway is the one you should memorise: whenever f_1 = o(f_2) (and both are nice), \mathrm{DTIME}(f_1) \subsetneq \mathrm{DTIME}(f_2) — for example \mathrm{DTIME}(n^2) \subsetneq \mathrm{DTIME}(n^3), a strict, provable gap.

Time-constructible functions

Why the fuss about "well-behaved"? The proof needs a machine that can count out its own time budget — otherwise it cannot know when to stop simulating. A function f(n) \ge n\log n is time-constructible if some TM, given 1^n, computes f(n) (say in binary) in O(f(n)) steps. Intuitively: the clock is affordable to build.

Happily, every function you'd ever name as a running time — n^2, n^3, n\log n, 2^n — is time-constructible. Pathological, wildly-varying functions are the only ones excluded, and they never arise as honest complexity bounds. Without this hypothesis the theorem genuinely fails: the gap theorem exhibits bizarre (non-constructible) bounds f where \mathrm{DTIME}(f) = \mathrm{DTIME}(2^f), an enormous budget increase buying nothing. Constructibility is exactly what rules such monsters out.

The proof: diagonalisation

The engine is the same one behind the undecidability of the halting problem — Cantor's diagonal argument — now run with a clock attached. We build a single language D that deliberately disagrees with every fast machine on at least one input, so no fast machine can decide it, yet D itself is decidable if you allow a little more time.

Build a machine \mathrm{Diag}. On input w, interpret w as the encoding \langle M \rangle of a Turing machine, then:

  1. Simulate M on input w for up to f(|w|) steps (using the constructible clock to count).
  2. If M halts within the budget and accepts, then \mathrm{Diag} rejects.
  3. Otherwise (M rejects, or runs past the budget), \mathrm{Diag} accepts.

By construction \mathrm{Diag} does the opposite of M on the input w = \langle M \rangle.

Now suppose, for contradiction, some machine M decided L(\mathrm{Diag}) in time o(f(n)). For inputs long enough, o(f) stays under the clock, so on w = \langle M \rangle the diagonal machine successfully simulates M to completion — and then answers the opposite of what M answers. So M and \mathrm{Diag} disagree on \langle M \rangle, contradicting that M decides the same language. Hence L(\mathrm{Diag}) \notin \mathrm{DTIME}(o(f)). And the clocked simulation itself runs in f(n)\log f(n), so L(\mathrm{Diag}) \in \mathrm{DTIME}(f\log f). That is the theorem.

Seeing the diagonal

Lay out an infinite table: row i is machine M_i, column j is input w_j = \langle M_j \rangle, and the cell records whether M_i accepts w_j within the time budget. The diagonal cell (i,i) is M_i's verdict on its own code. \mathrm{Diag} is the row you get by walking down the diagonal and flipping every entry — so it differs from M_i in column i, for every i. No row can equal it; no fast machine decides it.

The highlighted diagonal is the whole trick: by disagreeing with M_i in just one carefully chosen place, \mathrm{Diag} rules out every fast machine simultaneously. The clock is what makes each simulation finite — remove it and this becomes the halting-problem diagonal, which is undecidable at any budget.

Same diagonal, different clock. In the halting-problem argument you try to simulate M to completion with no time limit, so the diagonal machine can hang forever and is merely recognisable, not decidable. Here we cap the simulation at f(n) steps, which always halts, so \mathrm{Diag} is genuinely decidable — just not quickly. Bounding the resource converts an impossibility result into a separation result. That is the recurring magic of complexity theory: computability's undecidability proofs, run with a stopwatch, become statements about how much resource a problem needs.

The payoff: P ⊊ EXP

Chain the theorem across all polynomial budgets and you get the flagship corollary — a rare, unconditional separation of two named classes.

\mathrm{P} \;\subsetneq\; \mathrm{EXP}.

Because n^k = o(2^n) for every fixed k, the hierarchy theorem hands us a language decidable in (say) \mathrm{DTIME}(2^n) but in no polynomial time. So EXP strictly contains P — full stop, no assumptions.

This matters enormously: it proves that at least some separations in the grand chain \mathrm{L} \subseteq \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXP} are real. There are problems provably requiring exponential time. Complexity theory is not studying a mirage.

So why is P vs NP still open?

If diagonalisation cleanly separates P from EXP, why not point it at \mathrm{P} and \mathrm{NP}? The catch is that the hierarchy theorem separates a class from a larger version of the same resource (more time vs less time). P and NP use different resources — deterministic versus nondeterministic time — and the diagonal machine cannot simply "count steps" against a nondeterministic budget the same way.

Deeper still, relativization (the Baker–Gill–Solovay result) shows that any proof which, like diagonalisation, treats machines as black boxes must fail to settle P vs NP: there are oracles making \mathrm{P} = \mathrm{NP} and others making them differ, yet diagonalisation-style arguments hold relative to every oracle. So the very tool that so cleanly gives \mathrm{P} \subsetneq \mathrm{EXP} is provably too blunt for \mathrm{P} vs \mathrm{NP}. That is a large part of why the problem remains one of the deepest open questions in mathematics.

Two traps. First, the separation is only guaranteed when the budgets differ asymptotically: \mathrm{DTIME}(n^2) \subsetneq \mathrm{DTIME}(n^3) holds because n^2 = o(n^3), but a mere constant-factor increase, like \mathrm{DTIME}(n^2) versus \mathrm{DTIME}(3n^2), buys you nothing — they are the same class (constants are absorbed). Second, the theorem requires the larger bound to be time-constructible; drop that and the gap theorem builds counterexamples where doubling the exponent of the budget adds no power at all. "More time always helps" is true only with both fine-print conditions. State the theorem without them and you have stated something false.