Diagonalization and the Time Hierarchy Theorem

Cantor’s diagonal argument shows that the reals outnumber the integers by constructing, for any proposed enumeration, an element that differs from the $n$-th entry at position $n$. The time hierarchy theorem is the same argument run on machines, and its conclusion is that more time buys strictly more languages: for suitable bounds $f$ and $g$ with $f$ growing slower than $g$, there is a language decidable in time $g$ that is not decidable in time $f$. The construction is worth reading closely because it is the only general tool for separating classes, and because the conditions under which it works explain why it has not settled the questions that matter most.

The diagonal machine

Fix a bound $f$ that is at least linear and time-constructible: some machine computes $f(n)$ from a unary input of length $n$ in time $O(f(n))$. The theorem states $\mathrm{DTIME}(f(n)) \subsetneq \mathrm{DTIME}(f(n) \log f(n))$, and more generally $\mathrm{DTIME}(f(n)) \subsetneq \mathrm{DTIME}(g(n))$ for any $g$ that dominates $f \log f$ sufficiently.

The separating language is defined by a machine $D$ that takes an input $x$ and does the following:

1. Compute $f(|x|)$, using the constructibility assumption.
2. Interpret $x$ as the description of a machine $M$ in some fixed encoding. If $x$ is not a valid description, reject.
3. Simulate $M$ on input $x$ for at most $f(|x|)$ steps.
4. Accept if that simulation has not reached an accepting state by the end of the budget, and reject if it has.

The language $L(D)$ is the set of $x$ on which $D$ accepts. Two facts about $D$ are needed.

$D$ runs in time $O(f(n) \log f(n))$ on inputs of length $n$. The $\log f$ factor comes from the cost of simulating a machine whose description is being read from the input tape: the simulator must keep track of the simulated machine’s state and its head positions, and on a single-tape machine this requires scanning, which adds a logarithmic factor over the naive count. The exact factor depends on the simulation strategy; the theorem’s statement absorbs it into the bound.

$D$ disagrees with every machine that runs in time $f$. Take any machine $M$ with a time bound of $f(n)$, and consider $D$ on input $\langle M \rangle$, the encoding of $M$. The simulation of $M$ on its own description runs for $f(|\langle M \rangle|)$ steps, which is exactly the budget $M$ is allowed on that input. If $M$ accepts within the budget, $D$ rejects, so the two disagree. If $M$ does not accept within the budget, $D$ accepts, so again they disagree. Either way the languages differ on a specific input, which is enough to show they are not equal.

The diagonal step is the identification of the simulated machine with the input string. That is what makes the argument self-referential, and it is why the encoding must be effective: the map from machines to strings has to be computable, and the inverse map has to be computable too, so that $D$ can recover the machine from its description.

Why constructibility is not decoration

The bound $f$ must be computable by a machine within time proportional to itself. Without that condition, the diagonal machine cannot know when to stop simulating, and the argument has no budget to work with.

The condition is not vacuous: most functions one writes down are constructible, but some are not. A function that encodes the halting behaviour of a specific machine, say $f(n) = n^2$ if a particular machine halts and $n^3$ otherwise, is not computable at all, so it is certainly not time-constructible. A bound defined by a non-computable set is a real bound, but no machine can run against it, and the hierarchy theorem says nothing about it.

Space constructibility is the analogous condition for space bounds, and it is weaker in one direction: a machine can compute a space bound while using only that much space, which is easier than computing a time bound within that much time, because a computation can be replayed and the space reused. The space hierarchy theorem therefore separates bounds that differ by any constructible factor, without the logarithmic gap that the time version requires.

The gap and why it cannot be closed this way

The time hierarchy theorem separates $f$ from $f \log f$, not $f$ from $f + 1$. The gap is a consequence of the simulation overhead: to decide a language that a machine with bound $f$ cannot decide, the diagonal machine must simulate that machine, and simulation costs more than the simulated machine’s own running time. On a single-tape machine the overhead is at least a logarithmic factor, and no diagonalization argument known avoids it.

This is not a defect of the proof technique that could be repaired with more care. It is a consequence of the fact that a universal machine simulating another machine must spend time reading the other machine’s description, and that description is part of the input. The overhead is intrinsic to the act of simulation. Closing the gap would require a separation technique that does not go through simulation, and none is known.

The gap is also why the theorem says nothing about P versus NP. P is a union over all polynomial degrees, so any two polynomials $n^k$ and $n^{k+1}$ are both inside P, and the hierarchy theorem separates them as individual time classes without separating either from P. The theorem proves that $\mathrm{P} \subsetneq \mathrm{EXP}$, because $\mathrm{EXP}$ is a union over exponential degrees and contains languages outside every polynomial bound. It does not prove that $\mathrm{P} \subsetneq \mathrm{NP}$, and no amount of refinement of the diagonal argument will, because NP is not defined by a time bound alone.

What diagonalization can and cannot see

The technique has a precise reach, and knowing it prevents wasted effort.

It works whenever the class is defined by a resource bound and the machines in the class can be effectively enumerated. Deterministic time, deterministic space, nondeterministic time, and nondeterministic space all satisfy this, and each has a hierarchy theorem. The proofs differ in the simulation overhead and in the constructibility condition, not in the diagonal idea.

It fails for classes that are not defined by bounds on a single machine’s behaviour in a way that simulation can enumerate. The class P/poly is the clearest case. Its members are decided by circuit families rather than machines, and a circuit family may choose a completely different circuit at each length with no computable relationship between the choices. That freedom is not a technicality: P/poly contains undecidable languages. Every language has some circuit at each length, since a circuit can be built from that length’s truth table; the family is polynomial-size exactly when the language has small circuits at every length, and nothing requires those circuits to be computable from the length. A diagonal argument against circuit families cannot even start, because there is no machine to simulate whose behaviour the diagonal could contradict.

It fails, more importantly, for separating classes that are defined by different resources rather than different amounts of the same resource. P versus NP is a question about whether nondeterminism adds power at polynomial time, and the diagonal argument would need to simulate a nondeterministic machine deterministically, which is exactly the problem. A diagonal machine that simulates a nondeterministic machine has to explore a tree of computations, and the exploration cost is exponential in the depth unless the tree can be pruned, which is the content of the open problem.

The formal statement of this limitation is the relativization barrier: any proof that works by diagonalization and simulation relativizes, meaning it holds equally in the presence of an oracle, and there exist oracles relative to which P equals NP and oracles relative to which they differ. So no relativizing argument can settle the question. This is the subject of the oracle construction and its consequences, and it is the reason the hierarchy theorems, as general as they are, sit entirely on the safe side of the barrier.

The hierarchy as a ladder of classes

The practical value of the theorem is that it gives an infinite, strictly increasing sequence of classes inside exponential time. Between $\mathrm{DTIME}(n)$ and $\mathrm{DTIME}(2^n)$ there are infinitely many distinct levels, and the Ladner construction shows that a similar density holds inside NP if P differs from NP.

Statement	Status
$\mathrm{DTIME}(n) \subsetneq \mathrm{DTIME}(n^2)$	theorem, by diagonalization
$\mathrm{DTIME}(n^2) \subsetneq \mathrm{DTIME}(n^3)$	theorem, by diagonalization
$\mathrm{P} \subsetneq \mathrm{EXP}$	theorem, by diagonalization
$\mathrm{P} \subsetneq \mathrm{NP}$	open
$\mathrm{NP} \subsetneq \mathrm{PSPACE}$	open

The pattern in the table is exact: the proved separations are between classes defined by the same resource with different bounds, and the open ones are between classes defined by different resources or different modes of computation with the same bound. Diagonalization is a tool for the first kind of question and is blind to the second.

A small instance of the argument

The structure of the diagonal machine can be seen in a finite version that separates two classes of functions on a bounded domain, and the finite version is easier to hold in mind than the asymptotic one.

def diagonal(table, n):
    # table[i] is the truth table of the i-th function on inputs 0..n-1
    # return a function differing from every table entry
    out = [0] * n
    for i in range(min(n, len(table))):
        out[i] = 1 - table[i][i]      # differ from function i at input i
    return out

The function returned agrees with no entry in the table, because it differs from entry $i$ at position $i$. The cost is one bit flip per entry, and the returned function is a valid function on the same domain. Nothing about the construction is specific to computability; it is a combinatorial fact about the size of a function space versus the size of a list.

The asymptotic version adds three ingredients: the table is indexed by machine descriptions rather than by integers, the functions are languages rather than finite truth tables, and the diagonal function must be computable within a stated budget. The first two are bookkeeping. The third is where the theorem’s conditions come from, and where the gap between $f$ and $f \log f$ is paid for.