Time hierarchy theorem

Lore & Background

The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the universal Turing machine. The theorem states that for all time-constructible functions f(n), DTIME(o(f(n))) is strictly contained in DTIME(f(n) log f(n)). This shows that DTIME(n^a) is strictly contained in DTIME(n^b) if and only if a < b, giving an infinite time hierarchy. This theorem states that if g(n) is time-constructible and f(n+1) = o(g(n)), then NTIME(f(n)) is strictly contained in NTIME(g(n)). Both theorems use the notion of a time-constructible function, where a function f: N → N is time-constructible if there exists a deterministic Turing machine that, started with an input of n ones, halts after precisely f(n) steps. All polynomials with non-negative integer coefficients are time-constructible, as are exponential functions such as 2^n.

Reader's Guide

The time hierarchy theorems are central to computational complexity theory because they establish that the time-bounded hierarchy of complexity classes does not completely collapse. For deterministic Turing machines, the theorem shows that for every deterministic time-bounded complexity class, there is a strictly larger one. This means that problems requiring more time are genuinely harder, and there is no upper bound on the time needed to solve all problems. The theorem for nondeterministic Turing machines provides a similar hierarchy for nondeterministic time classes. The proofs use diagonalization, constructing a machine that cannot be in the smaller time class but can be simulated in the larger one. The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of advice. The results have implications for the P versus NP problem and the structure of complexity classes, as they show that time resources create an infinite hierarchy of distinct classes.

Did You Know?

• All polynomials with non-negative integer coefficients are time-constructible functions.

Historical Development and Key Contributors

Stearns and Juris Hartmanis established the foundational result for multi-tape Turing machines. Their work demonstrated that granting a machine additional time genuinely expands the set of problems it can decide. A year later, F. C. Hennie and Stearns refined the framework by improving the efficiency of the universal Turing machine used in the argument, sharpening the quantitative gap between complexity classes. The nondeterministic variant followed a longer path.

Core Statement and the Infinite Hierarchy

At its heart, the deterministic time hierarchy theorem asserts a strict separation: for any time-constructible function f(n), the class of problems solvable in asymptotically less than f(n) steps is a proper subset of those solvable within f(n) log f(n) steps. This logarithmic overhead is the price of the simulation argument that underlies the proof. A direct and striking corollary is that DTIME(n^a) is strictly contained in DTIME(n^b) whenever a is less than b, yielding an infinite ascending ladder of complexity classes. No finite list of polynomial-time classes exhausts all deterministic computation; there is always a next rung. The nondeterministic version is stated slightly differently: if g(n) is time-constructible and f(n+1) grows strictly slower than g(n) in the little-o sense, then NTIME(f(n)) is a proper subset of NTIME(g(n)). Both theorems guarantee that the time-bounded hierarchy never fully collapses into a single class.

Proof Strategy and Technical Machinery

The proof strategy for both theorems rests on two pillars: diagonalization and simulation. To show that a larger time class strictly contains a smaller one, one constructs a decision problem that provably evades every machine running within the tighter bound. This is achieved through a diagonalization argument, where the constructed machine systematically disagrees with each candidate machine in the smaller class on some input. The second pillar is a universal simulator: a single machine capable of emulating any other machine of a given description, and the proof must show that this simulation fits within the larger time budget. A critical technical ingredient is the notion of a time-constructible function, a mapping from natural numbers to natural numbers for which there exists a deterministic Turing machine that, given n ones as input, halts after exactly f(n) steps. All polynomials with non-negative integer coefficients and exponential functions like 2^n satisfy this condition, ensuring the theorems apply to the most commonly studied time bounds.

Scope, Limitations, and Related Results

The time hierarchy theorems sit alongside their space-bounded counterparts, the space hierarchy theorems, which impose analogous strict separations on space usage. Together they form a backbone of structural complexity theory, confirming that resources—whether time or space—genuinely stratify computational power. However, the landscape is not uniformly settled. For time-bounded probabilistic complexity classes, no analogous hierarchy theorem is currently known, unless the class is augmented with at least one bit of advice. This gap highlights that randomness introduces subtleties absent from the deterministic and nondeterministic settings. The theorems also carry a practical message: in complexity-theoretic terms, there exist problems decidable in quadratic time that resist any linear-time algorithm, and this separation is not an artifact of our current inability to find better algorithms but a provable, structural fact about the limits of computation.