Time hierarchy theorem

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.^[1] It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the Universal Turing machine.^[2] 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.^[3] It was improved to its current form via a complex proof by Joel Seiferas, Michael Fischer, and Albert Meyer in 1978.^[4] Finally in 1983, Stanislav Žák achieved the same result with the simple proof taught today.^[5] 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.^[6]