In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with n² time but not n time, where n is the input length.

The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965. It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the universal Turing machine. Consequent to the theorem, for every deterministic time-bounded complexity class, there is a strictly larger time-bounded complexity class, and so the time-bounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all time-constructible functions f(n), $${\displaystyle {\mathsf {DTIME}}\left(o\left(f(n)\right)\right)\subsetneq {\mathsf {DTIME}}(f(n){\log f(n)}),}$$ where DTIME(f(n)) denotes the complexity class of decision problems solvable in time O(f(n)). The left-hand class involves little o notation, referring to the set of decision problems solvable in asymptotically less than f(n) time.

In particular, this shows that ${\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})}$ if and only if ${\displaystyle a<b}$, so we have an infinite time hierarchy.

The time hierarchy theorem for nondeterministic Turing machines was originally proven by Stephen Cook in 1972. It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978. Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today. The time hierarchy theorem for nondeterministic Turing machines states that if g(n) is a time-constructible function, and f(n+1) = o(g(n)), then $${\displaystyle {\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n)).}$$

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.

Both theorems use the notion of a time-constructible function. A function ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ is time-constructible if there exists a deterministic Turing machine such that for every ${\displaystyle n\in \mathbb {N} }$, if the machine is started with an input of n ones, it will halt after precisely f(n) steps. All polynomials with non-negative integer coefficients are time-constructible, as are exponential functions such as 2ⁿ.

We need to prove that some time class TIME(g(n)) is strictly larger than some time class TIME(f(n)). We do this by constructing a machine which cannot be in TIME(f(n)), by diagonalization. We then show that the machine is in TIME(g(n)), using a simulator machine.

Time Hierarchy Theorem. If f(n) is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic time o(f(n)) but can be solved in worst-case deterministic time O(f(n)log f(n)). Thus