In computational complexity theory, the time hierarchy theorems are important statements about timebounded 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^{2} time but not n time.
The time hierarchy theorem for deterministic multitape 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 timebounded complexity class, there is a strictly larger timebounded complexity class, and so the timebounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all timeconstructible functions f(n),

\mathbf{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right) \subsetneq \mathbf{DTIME}(f(n)).
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 timeconstructible function, and f(n) = o(g(n)), then

\mathbf{NTIME}(f(n)) \subsetneq \mathbf{NTIME}(g(n)).
The analogous theorems for space are the space hierarchy theorems. A similar theorem is not known for timebounded probabilistic complexity classes, unless the class also has advice.^{[6]}
Contents

Background 1

Proof overview 2

Deterministic time hierarchy theorem 3

Statement 3.1

Proof 3.2

Extension 3.3

Nondeterministic time hierarchy theorem 4

Consequences 5

See Also 6

References 7
Background
Both theorems use the notion of a timeconstructible function. A function f:\mathbb{N}\rightarrow\mathbb{N} is timeconstructible if there exists a deterministic Turing machine such that for every 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 nonnegative integral coefficients are timeconstructible, as are exponential functions such as 2^{n}.
Proof overview
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.
Deterministic time hierarchy theorem
Statement
Time Hierarchy Theorem. If f(n) is a timeconstructible function, then there exists a decision problem which cannot be solved in worstcase deterministic time f(n) but can be solved in worstcase deterministic time f(n)^{2}. In other words,

\mathbf{DTIME}(f(n)) \subsetneq \mathbf{DTIME}\left (f(n)^2 \right).
Note 1. f(n) is at least n, since smaller functions are never timeconstructible.
Note 2. Even more generally, it can be shown that if f(n) is timeconstructible, then

\mathbf{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right)\subsetneq \mathbf{DTIME}\left (f(n) \right).
For example, there are problems solvable in time n^{2} but not time n, since n is in

o\left(\frac{n^2}{\log {n^2}}\right).
Proof
We include here a proof that DTIME(f(n)) is a strict subset of DTIME(f(2n + 1)^{3}) as it is simpler. See the bottom of this section for information on how to extend the proof to f(n)^{2}.
To prove this, we first define a language as follows:

H_f = \left\{ ([M], x)\ \ M \ \mbox{accepts}\ x \ \mbox{in}\ f(x) \ \mbox{steps} \right\}.
Here, M is a deterministic Turing machine, and x is its input (the initial contents of its tape). [M] denotes an input that encodes the Turing machine M. Let m be the size of the tuple ([M], x).
We know that we can decide membership of H_{f} by way of a deterministic Turing machine that first calculates f(x), then writes out a row of 0s of that length, and then uses this row of 0s as a "clock" or "counter" to simulate M for at most that many steps. At each step, the simulating machine needs to look through the definition of M to decide what the next action would be. It is safe to say that this takes at most f(m)^{3} operations, so

H_f \in \mathbf{TIME}(f(m)^3).
The rest of the proof will show that

H_f \notin \mathbf{TIME}(f( \left\lfloor \tfrac{m}{2} \right\rfloor ))
so that if we substitute 2n + 1 for m, we get the desired result. Let us assume that H_{f} is in this time complexity class, and we will attempt to reach a contradiction.
If H_{f} is in this time complexity class, it means we can construct some machine K which, given some machine description [M] and input x, decides whether the tuple ([M], x) is in H_{f} within

\mathbf{TIME}(f( \left\lfloor \tfrac{m}{2} \right\rfloor )).
Therefore we can use this K to construct another machine, N, which takes a machine description [M] and runs K on the tuple ([M], [M]), and then accepts only if K rejects, and rejects if K accepts. If now n is the length of the input to N, then m (the length of the input to K) is twice n plus some delimiter symbol, so m = 2n + 1. N's running time is thus

\mathbf{TIME}(f( \left\lfloor \tfrac{m}{2} \right\rfloor )) = \mathbf{TIME}(f( \left\lfloor \tfrac{2n+1}{2} \right\rfloor )) = \mathbf{TIME}(f(n)).
Now if we feed [N] as input into N itself (which makes n the length of [N]) and ask the question whether N accepts its own description as input, we get:

If N accepts [N] (which we know it does in at most f(n) operations), this means that K rejects ([N], [N]), so ([N], [N]) is not in H_{f}, and thus N does not accept [N] in f(n) steps. Contradiction!

If N rejects [N] (which we know it does in at most f(n) operations), this means that K accepts ([N], [N]), so ([N], [N]) is in H_{f}, and thus N does accept [N] in f(n) steps. Contradiction!
We thus conclude that the machine K does not exist, and so

H_f \notin \mathbf{TIME}(f( \left\lfloor \tfrac{m}{2} \right\rfloor )).
Extension
The reader may have realised that the proof is simpler because we have chosen a simple Turing machine simulation for which we can be certain that

H_f \in \mathbf{TIME}(f(m)^3).
It has been shown^{[7]} that a more efficient model of simulation exists which establishes that

H_f \in \mathbf{TIME}(f(m) \log f(m))
but since this model of simulation is rather involved, it is not included here.
Nondeterministic time hierarchy theorem
If g(n) is a timeconstructible function, and f(n+1) = o(g(n)), then there exists a decision problem which cannot be solved in nondeterministic time f(n) but can be solved in nondeterministic time g(n). In other words, the complexity class NTIME(f(n)) is a strict subset of NTIME(g(n)).
Consequences
The time hierarchy theorems guarantee that the deterministic and nondeterministic versions of the exponential hierarchy are genuine hierarchies: in other words P \subsetneq EXPTIME \subsetneq 2EXP \subsetneq ... and NP \subsetneq NEXPTIME \subsetneq 2NEXP \subsetneq ....
For example, \mathbf{P} \subsetneq \mathbf{EXPTIME} since \mathbf{P} \subseteq \mathbf{DTIME} (2^n)\subsetneq \mathbf{DTIME} (2^{2n}) \subseteq \mathbf{EXPTIME}. Indeed \mathbf{DTIME}\left(2^n\right) \subseteq \mathbf{DTIME}\left(o\left(\frac{2^{2n}}{2n}\right)\right) \subsetneq \mathbf{DTIME}(2^{2n}) form the time hierarchy theorem.
The theorem also guarantees that there are problems in P requiring arbitrary large exponents to solve; in other words, P does not collapse to DTIME(n^{k}) for any fixed k. For example, there are problems solvable in n^{5000} time but not n^{4999} time. This is one argument against Cobham's thesis, the convention that P is a practical class of algorithms. If such a collapse did occur, we could deduce that P ≠ PSPACE, since it is a wellknown theorem that DTIME(f(n)) is strictly contained in DSPACE(f(n)).
However, the time hierarchy theorems provide no means to relate deterministic and nondeterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of computational complexity theory: whether P and NP, NP and PSPACE, PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not.
See Also
References

^

^ Hennie, F. C.;

^

^ Seiferas, Joel I.;

^ Stanislav, Žák (October 1983). "A Turing machine time hierarchy". Theoretical Computer Science (Elsevier Science B.V.) 26 (3): 327–333.

^ Fortnow, L.; Santhanam, R. (2004). "45th Annual IEEE Symposium on Foundations of Computer Science". p. 316.

^ Luca Trevisan, Notes on Hierarchy Theorems, U.C. Berkeley

Pages 310–313 of section 9.1: Hierarchy theorems.

Section 7.2: The Hierarchy Theorem, pp. 143–146.
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.