The Time and Space Hierarchy Theorems

A complexity class hierarchy theorem asserts that increasing a resource bound (time or space) by enough of a margin creates a language decidable in the larger bound but not in the smaller one. To even state such a theorem we need the bound function $f(n)$ itself to be computable without blowing past the budget it describes — otherwise a machine cannot know when to stop simulating. A function $f : \mathbb{N} \to \mathbb{N}$ is time-constructible if there is a Turing machine that, given input $1^n$ (the unary string of length $n$), outputs the binary representation of $f(n)$ using $O(f(n))$ steps. It is space-constructible if some machine computes $f(n)$ from $1^n$ using $O(f(n))$ space. Nearly every function you would write down — $n$, $n\log n$, $n^2$, $2^n$ — is constructible; pathological non-constructible functions are needed only to build counterexamples showing the theorems are tight. The two theorems are:

Time Hierarchy Theorem. If $f$ is time-constructible and $f(n)\log f(n) = o(g(n))$, then

Space Hierarchy Theorem. If $f$ is space-constructible and $f(n) = o(g(n))$, then

Notice the asymmetry: time needs a $\log f(n)$ overhead margin, space needs none. This is not a proof artifact to be waved away — it reflects a genuine simulation cost. Simulating one Turing machine by another (a universal simulation) using a single-tape or fixed-alphabet machine multiplies running time by a logarithmic factor (bookkeeping to track another machine's head position and state costs extra steps per step), whereas simulating another machine's space usage costs no asymptotic space overhead — you can reuse the same tape cells to track another machine's tape cells with only a constant multiplicative factor. This single fact — that space simulation is "free" while time simulation is "log-costly" — is the entire reason the two theorems have different gap requirements, and is worth remembering as the one sentence that explains both proofs simultaneously.

Both proofs follow the same three-step recipe: (1) fix an enumeration of all Turing machines, (2) build a universal diagonalizer $D$ that on input $w$ interprets $w$ itself as encoding a machine $M_w$, simulates $M_w$ on $w$ within the target resource bound $g(n)$, and outputs the opposite of what $M_w$ outputs, (3) argue $D \in$ the $g$-bounded class but $D \notin$ the $f$-bounded class, because if some $f$-bounded machine $M$ decided the same language as $D$, feeding $D$ the description of $M$ produces a direct contradiction.

Step-by-step construction of the diagonalizer

``` // D is a Turing machine with two behaviors, parameterized by g(n) // Input: a string w of length n, interpreted as possibly with padding procedure D(w): n := length(w) budget := compute g(n) // uses constructibility of g M := decode(w) // extract a TM description from w // (if w does not parse, treat M as // a fixed reject-everything machine) result := SIMULATE(M, w, budget) // runs M on input w for at most `budget` steps (time version) // or within `budget` tape cells (space version) // if M has not halted when the budget is exhausted, treat result as REJECT if result == ACCEPT: return REJECT else: return ACCEPT ``` The crucial subroutine is `SIMULATE`, a universal machine that runs an arbitrary encoded machine $M$ on input $w$ while enforcing a hard resource ceiling. Its efficiency determines whether $D$ itself fits inside $\mathsf{DTIME}(g(n))$ or $\mathsf{SPACE}(g(n))$.

• Time version. A single-tape universal simulator can simulate $t$ steps of a $k$-tape machine $M$ in $O(t \log t)$ steps, because each simulated step requires scanning across a representation of $M$'s tapes whose relevant portion has grown to length $O(t)$, and locating/updating symbols costs an extra $O(\log t)$ factor with an efficient encoding. So simulating $M$ for up to $g(n)$ steps costs $D$ about $O(g(n)\log g(n))$ steps of its own. For $D$ to run within its own time budget $O(g(n))$, we actually design $D$'s target class as $\mathsf{DTIME}(g(n))$ where $g$ was chosen with the log slack already built in — this is precisely why the theorem's hypothesis is $f(n)\log f(n) = o(g(n))$ rather than just $f(n) = o(g(n))$: we need $g$ itself to have room to absorb the $\log$ overhead of simulating machines bounded by $f$.

• Space version. A universal simulator can track another machine's configuration using only $O(1)$ extra tape cells beyond what $M$ itself uses (storing $M$'s current state, head positions as tape markers, and reusing $M$'s own tape layout rather than copying it). So simulating $M$ within space $f(n)$ costs $D$ only $O(f(n))$ space, with no logarithmic penalty — hence no log slack is needed in the space theorem's hypothesis.

• The clock/ruler and the diagonal trick. In both versions, `SIMULATE` must enforce the budget: for time, $D$ maintains a counter (itself costing only a constant multiplicative overhead to store and increment) and aborts the simulation, treating $M$ as rejecting, if $M$ has not halted after `budget` steps; for space, $D$ marks off a fixed number of tape cells (using the constructed value $g(n)$ as a literal boundary marker) and aborts if $M$ tries to leave that region. This is why constructibility is required: $D$ must be able to compute $g(n)$ itself, within the same resource bound, in order to know where to place the clock or the ruler.

• Self-reference via encoding. Because $w$ is simultaneously "the input" and "the description of the machine being simulated," $D$ is diagonalizing against all machines, including itself, in the classic Cantor/Turing style. If some machine $M^*$ with encoding $\langle M^* \rangle$ decides the same language as $D$ using resource $f(n)$, then running $D$ on input $w = \langle M^*\rangle$ must simultaneously equal `SIMULATE`$(M^*, \langle M^*\rangle)$'s result (since $D$ agrees with $M^*$ everywhere, by assumption) and also equal the flip of that result (by $D$'s own definition) — a contradiction, provided the simulation actually completes within budget, which the resource gap guarantees.

Correctness of the Time Hierarchy Theorem. Let $g$ satisfy $f(n)\log f(n) = o(g(n))$ with $g$ time-constructible (the standard statement assumes $g$ itself is time-constructible so $D$ can compute its own clock; some textbook variants only require $f$ constructible and phrase the gap differently, but the constructible-$g$ version is the clean one to prove). Define $D$ as above with `SIMULATE` implementing a universal simulator that charges $O(t\log t)$ steps to simulate $t$ steps of an arbitrary machine. Then: 1. $D$ runs in time $O(g(n))$: computing $g(n)$ costs $O(g(n))$ by constructibility, and simulating up to $g(n)$ steps of $M_w$ costs $O(g(n)\log g(n))$ — wait, this needs care. The standard resolution: we simulate $M_w$ for up to $f(n)$ steps (not $g(n)$), aborting and rejecting if $M_w$ hasn't halted by then, costing $O(f(n)\log f(n))$, which is $o(g(n))$ by hypothesis; the extra $O(g(n))$ overhead for computing the clock and bookkeeping keeps the total at $O(g(n))$. So $D \in \mathsf{DTIME}(g(n))$. 2. No machine $M$ deciding $D$'s language runs in time $O(f(n))$. Suppose $M$ decides $L(D)$ and runs in time $O(f(n))$. By the padding/encoding scheme there are infinitely many strings $w$ with $w = \langle M \rangle$ (via padding, since a machine has infinitely many equivalent encodings of growing length), each long enough that the simulation budget $f(n)$ exceeds $M$'s actual running time on that particular $w$. Feeding such a $w$ to $D$: $D$ simulates $M$ on $w$ to completion within the allotted $f(n)$ steps (since $M$'s real running time is $O(f(n))$ and the constant/padding is chosen large enough), obtains $M(w)$'s true answer, and outputs the opposite. So $D(w) \neq M(w)$. But $M$ was assumed to decide $L(D)$, i.e. $M(w) = D(w)$ for all $w$ — contradiction. Hence no $f(n)$-time machine decides $L(D)$, so $L(D) \in \mathsf{DTIME}(g(n)) \setminus \mathsf{DTIME}(f(n))$. The padding argument deserves a note: to make the "infinitely many $w$ with $w=\langle M\rangle$ and $w$ long enough" step work rigorously, one fixes an encoding scheme where a machine can be padded with unused suffix symbols to reach any larger length while computing the same function, which is a standard, harmless technicality.

Correctness of the Space Hierarchy Theorem. The structure is identical but the arithmetic is friendlier because of the free space simulation. Let $f(n) = o(g(n))$ with $g$ space-constructible. Build $D$ identically, except `SIMULATE` uses a space-efficient universal simulator: tracking $M$'s configuration (state, head positions, relevant tape contents) costs only $O(1)$ extra cells beyond $M$'s own usage, so simulating a machine using $s$ space costs $D$ only $O(s)$ space. Then: 1. $D \in \mathsf{SPACE}(g(n))$: computing $g(n)$ costs $O(g(n))$ space (constructibility), and simulating $M_w$ within an $f(n)$-cell budget costs $O(f(n)) = o(g(n))$ space — well within the $g(n)$ ceiling. 2. By the same contradiction argument, no $f(n)$-space machine can decide $L(D)$: if $M$ used space $O(f(n))$ and decided $L(D)$, then on a suitably padded encoding $w=\langle M\rangle$, $D$ simulates $M$ to completion within space $f(n)$, learns $M(w)$, and outputs the opposite, contradicting $M$ deciding $L(D)$. So $L(D) \in \mathsf{SPACE}(g(n)) \setminus \mathsf{SPACE}(f(n))$, giving the strict containment, with no logarithmic slack required — precisely because space, unlike time, can be reused by a simulator rather than paid for again.

Why the gaps are necessary, not artifacts. These are not proof-technique laziness; sub-quadratic-ish gaps for time genuinely can fail to separate classes in some models, and the linear speedup theorem for space (space usage can be divided by any constant via a larger tape alphabet) is exactly why the space theorem's threshold is a clean little-o with no constant slack needed either — constant factors in space don't matter at all, unlike in time where constant factors are already absorbed by the linear speedup theorem for time but the log factor from universal simulation survives that speedup and must be paid explicitly.

Complexity of the theorems' "output." The theorems themselves are proved in polynomial-in-$g(n)$ meta-time (constructing $D$'s tape and running the simulation), which is irrelevant to their content — the theorems are statements about which languages fall into which resource classes, not about the runtime of the proof. The one honest caveat: the theorems give existence of a separating language, typically an artificial diagonal language, not a natural or interesting one; showing a specific natural problem (like SAT) requires more than $O(n)$ time or more than $O(\log n)$ space is a separate, often open, question.

Concretely instantiate the Time Hierarchy Theorem with $f(n) = n^2$ and check whether $g(n) = n^3$ gives a valid separation, then check a tempting but invalid attempt with $g(n) = n^2 \log n$ vs. a bigger $f$.

Case A: $f(n) = n^2$, $g(n) = n^3$. Check the hypothesis: is $f(n)\log f(n) = n^2 \log(n^2) = 2n^2\log n = o(n^3)$? Yes — $n^2 \log n$ grows strictly slower than $n^3$ for large $n$ (polynomial beats polylog-times-lower-polynomial). So the theorem applies:

So there genuinely exist languages decidable in cubic time but not quadratic time.

Case B: a tempting but failing attempt — $f(n) = n^2$, $g(n) = n^2 \log\log n$. Check: is $n^2\log(n^2) = 2n^2\log n = o(n^2\log\log n)$? No — $\log n$ grows faster than $\log\log n$, so $n^2 \log n$ is not $o(n^2\log\log n)$; in fact $n^2\log n$ eventually dominates $n^2 \log\log n$. The hypothesis fails, and indeed the proof breaks concretely: $D$ would need $O(n^2\log n)$ steps just to simulate an $f$-bounded machine, but its own budget is only $O(n^2\log\log n)$ — the simulation cannot finish inside $D$'s own allowance, so $D$ does not fit in $\mathsf{DTIME}(g(n))$ and the argument collapses. This is why the theorem's stated gap is not cosmetic: shrink it and the diagonalizing machine literally cannot afford to diagonalize.

Case C: the space version, for contrast. Take $f(n) = n$, $g(n) = n\log n$. Check $f(n) = o(g(n))$: yes, trivially, $n = o(n\log n)$. No log-squared correction needed anywhere — the simulator tracking a linear-space machine costs only $O(n)$ extra space, safely inside the $O(n\log n)$ budget with enormous room to spare. This gives

a separation that would have needed a far bigger gap in the time setting to survive the log-overhead of universal simulation.

The hierarchy theorems emerged from the same wave of foundational work that gave rise to complexity theory as a discipline distinct from computability theory — the shift from asking "can this be computed at all?" to "how much resource does computing it cost?" The time hierarchy theorem is due to Hartmanis and Stearns, whose 1965 paper is often cited as the founding document of computational complexity theory; the space hierarchy and related tape-complexity results grew out of the same collaboration and subsequent work with Lewis.

Hierarchy theorems are invoked wherever someone needs a guaranteed separation rather than a conjectured one. Compiler and runtime engineers rely implicitly on the intuition these theorems formalize: allocating an algorithm more time or memory really can unlock strictly more capability, not just faster constants — this is the theoretical bedrock beneath the entire practice of algorithmic complexity analysis taught alongside Measuring Time Complexity and Measuring Space Complexity. In cryptography, hardness assumptions often implicitly lean on hierarchy-style intuition (that exponential time genuinely outclasses polynomial time) even though the specific cryptographic hardness assumptions themselves remain unproven; the hierarchy theorems are the closest thing we have to a proven instance of "more resources help," which grounds why such assumptions are plausible rather than absurd. In complexity theory pedagogy and research, the theorems are the standard first example of an unconditional separation, contrasted immediately with $\mathsf{P}$ vs $\mathsf{NP}$, to teach students what a proof of inequality between complexity classes actually looks like. They underlie the proof that the class L is strictly contained in PSPACE (via the chain $\mathsf{L} \subsetneq \mathsf{SPACE}(\log^2 n) \subsetneq \cdots \subsetneq \mathsf{PSPACE}$), and they justify why researchers studying the Polynomial Hierarchy believe its levels are plausibly distinct even without proof, by analogy to the proven strictness of the time and space towers. They also inform time-space tradeoff arguments used when analyzing randomized classes such as BPP, where derandomization results must respect the fact that time and space resources are provably not fungible without cost.

Ask the tutor: How does the padding argument formally guarantee infinitely many valid input lengths for the diagonalization contradiction?