# 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*^{2} time but not *n* time.

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*),

- .

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*) = o(*g*(*n*)), then

- .

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 advice.^{[6]}

## Contents

## Background

Both theorems use the notion of a time-constructible function. A function is time-constructible if there exists a deterministic Turing machine such that for every , if the machine is started with an input of *n* ones, it will halt after precisely *f*(*n*) steps. All polynomials with non-negative integral coefficients are time-constructible, 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.Iff(n) is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic timef(n) but can be solved in worst-case deterministic timef(n)^{2}. In other words,

**Note 1.** *f*(*n*) is at least *n*, since smaller functions are never time-constructible.

**Note 2.** Even more generally, it can be shown that if *f*(*n*) is time-constructible, then

For example, there are problems solvable in time *n*^{2} but not time *n*, since *n* is in

### Proof

We include here a proof that **DTIME**(*f*(*n*)) is a strict subset of **DTIME**(*f*(2*n* + 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:

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

The rest of the proof will show that

so that if we substitute 2*n* + 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*within

_{f}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* = 2*n* + 1. *N*'s running time is thus

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*, and thus_{f}*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*, and thus_{f}*N***does**accept [*N*] in*f*(*n*) steps. Contradiction!

We thus conclude that the machine *K* does not exist, and so

### 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

It has been shown^{[7]} that a more efficient model of simulation exists which establishes that

but since this model of simulation is rather involved, it is not included here.

## Non-deterministic time hierarchy theorem

If *g*(*n*) is a time-constructible function, and *f*(*n*+1) = o(*g*(*n*)), then there exists a decision problem which cannot be solved in non-deterministic time *f*(*n*) but can be solved in non-deterministic 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 non-deterministic versions of the exponential hierarchy are genuine hierarchies: in other words **P** **EXPTIME** **2-EXP** ... and **NP** **NEXPTIME** **2-NEXP** ....

For example, since . Indeed from the time hierarchy theorem.

The theorem also guarantees that there are problems in **P** requiring arbitrarily 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 well-known theorem that **DTIME**(*f*(*n*)) is strictly contained in **DSPACE**(*f*(*n*)).

However, the time hierarchy theorems provide no means to relate deterministic and non-deterministic 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

- ↑ Hartmanis, J.; Stearns, R. E. (1 May 1965). "On the computational complexity of algorithms".
*Transactions of the American Mathematical Society*. American Mathematical Society.**117**: 285–306. ISSN 0002-9947. JSTOR 1994208. MR 0170805. doi:10.2307/1994208. - ↑ Hennie, F. C.; Stearns, R. E. (October 1966). "Two-Tape Simulation of Multitape Turing Machines".
*J. ACM*. New York, NY, USA: ACM.**13**(4): 533–546. ISSN 0004-5411. doi:10.1145/321356.321362. - ↑ Cook, Stephen A. (1972). "A hierarchy for nondeterministic time complexity".
*Proceedings of the fourth annual ACM symposium on Theory of computing*. STOC '72. Denver, Colorado, United States: ACM. pp. 187–192. doi:10.1145/800152.804913. - ↑ Seiferas, Joel I.; Fischer, Michael J.; Meyer, Albert R. (January 1978). "Separating Nondeterministic Time Complexity Classes".
*J. ACM*. New York, NY, USA: ACM.**25**(1): 146–167. ISSN 0004-5411. doi:10.1145/322047.322061. - ↑ Stanislav, Žák (October 1983). "A Turing machine time hierarchy".
*Theoretical Computer Science*. Elsevier Science B.V.**26**(3): 327–333. doi:10.1016/0304-3975(83)90015-4. - ↑ Fortnow, L.; Santhanam, R. (2004). "45th Annual IEEE Symposium on Foundations of Computer Science": 316. ISBN 0-7695-2228-9. doi:10.1109/FOCS.2004.33.
`|chapter=`

ignored (help) - ↑ Luca Trevisan, Notes on Hierarchy Theorems, U.C. Berkeley

- Michael Sipser (1997).
*Introduction to the Theory of Computation*. PWS Publishing. ISBN 0-534-94728-X. Pages 310–313 of section 9.1: Hierarchy theorems. - Christos Papadimitriou (1993).
*Computational Complexity*(1st ed.). Addison Wesley. ISBN 0-201-53082-1. Section 7.2: The Hierarchy Theorem, pp. 143–146.