In computational complexity theory, the time hierarchy theorems are important statements that ensure the existence of certain "hard" problems which cannot be solved in a given amount of time. As a consequence, for every time-bounded complexity class, there is a strictly larger time-bounded complexity class, and so the run-time hierarchy of problems does not completely collapse. One theorem deals with deterministic computations and the other with non-deterministic ones. The analogous theorems for space are the space hierarchy theorems. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions. ...

Both theorems use the notion of a time-constructible function. A function f : N → N is time-constructible if there exists a deterministic Turing machine such that for every n in 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 integral coefficients are time-constructible, as are exponential functions such as 2ⁿ. In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n). ... In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ... The Turing Machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. The concept is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... In mathematics, polynomial functions, or polynomials, are an important class of simple and smooth functions. ...

Deterministic time hierarchy theorem

Statement

For any time constructible function , there exists a language A that is decidable in time O(t(n)) but not in time o(t(n) / logt(n)). In complexity theory, a time-constructible function is a function f from natural numbers to natural numbers with the property that f(n) can be constructed from n by a Turing machine in the time of order f(n). ...

Proof

We prove this by constructing a Turing machine B that is a O(t(n)) decider for a language A that is not decidable in o(t(n) / logt(n)) time. In order to ensure that B finishes its computation in time O(t(n)) we include in B a counter of length logt(n), which is the number of bits required to store the number O(t(n)).

There are two parts to this construction. One part is to ensure that B has a different output from all o(t(n) / logt(n)) Turing machines. We do this by simulating a given Turing machine M on input . If M finishes its computation quickly enough (in time less than t(n) / logt(n) where n is the length of the input string), we construct B to have the opposite output (this is similar to the digitalisation technique explained in the Diagonalization Lemma). But what if M does not halt in the alloted time? we still need to make sure that B is a O(t(n)) decider, so we add a counter to B to make sure that it stops after t(n) steps. In mathematical logic, the diagonalization lemma states that for any well formed formula with a free variable x, there is a sentence ψ such that where [ψ] is the Gödel number for ψ. ...

The basic structure of TM B is:

 input: string w with length n if w 6  for some TM M then reject end if calculate  and use this value to create counter c while c > 0 do simulate M with input w for 1 step if M accepts then reject else if M rejects then accept end if decrement c end while reject 

Now we need to show that B halts within O(t(n)) time. In order to simulate M, B needs to keep track of M's state, the tape symbol M is currently reading, and M's transition function. If B were to store this information in one spot on its tape, as B simulates M B may have to spend an arbitrary amount of time moving traveling back and forth retrieving this information about M. So we introduce a notion of tracks on B's tape. In one track we will store information about M, in the other track we will store information about B's current computation. We change B's tape alphabet to a set of pairs, one from each track. Then, in a constant amount of time (dependent on the length of M, not the length of the entire input string w) B can copy the information on the first track to the current location on the second track. So, if M runs in time g(n), B can simulate it in time O(g(n)). We add the counter to a third tape (also to cut down on unbounded time of traveling between the current head position of B and the clock). The actual clock updating operations require only O(logt(n)) because the length of the clock is log(t(n) / logt(n)). So, if we allow B to execute for steps and each step requires O(logt(n)) time, B will halt in time O(t(n)).

Formally we need to show that A is not decidable in o(t(n) / logt(n)) time. We prove this by contradiction. Assume that TM M decides A in time g(n), which is o(t(n) / logt(n)). Then B can simulate M in time for some constant d. So, for some constant n₀, for all . Consider what happens when we run B on input . This input is longer than n₀, which means that B will have time to simulate M until it halts and then B will do the opposite of M on the same input. Thus, M does not decide A which contradicts our assumption. So, A is not decidable in o(t(n) / logt(n)) time.

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)). The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... In computational complexity theory, the complexity class NTIME(f(n)) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(f(n)), and unlimited space. ...

Corollaries

Corrollary 1

For any two functions t₁, , where t₁(n) is o(t₂(n)/logt₂(n)) and t₂ is time constructible, TIME(t₁(n)) TIME(t₂(n)).

This corollary shows that t₁ and t₂ belong to two different classes of TIME hierarchies (and that TIME(t₂) includes TIME(t₁). Note that we can say the two classes are different because TIME(t₁) is a strict subset of TIME(t₂).

Corrollary 2

For any two real number , TIME() TIME()

This corollary shows that polynomials of different degree are in different TIME hierarchies and that the classes of the smaller degree polynomials are strict subsets of the classes of the larger degree polynomials.

Corrollary 3

By this corollary, the classes of polynomial time algorithms and exponential time algorithms are different.

Consequences

The time hierarchy theorems guarantee that the deterministic and non-deterministic version of the exponential hierarchy are genuine hierarchies: in other words P ⊂ EXPTIME ⊂ 2-EXP ⊂ ..., and NP ⊂ NEXPTIME ⊂ 2-NEXP ⊂ ... In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, starting with EXP: and continuing with and so on. ... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time O(2p(n)) for some polynomial p(n), and unlimited space. ...

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 O(n⁵⁰⁰⁰) time but not O(n⁴⁹⁹⁹) time. This is one argument against considering P to be a practical class of algorithms. This is unfortunate, since 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 complexity theory: whether P and NP, NP and PSPACE, PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not. Complexity theory can refer to more than one thing: Computational complexity theory: a field in theoretical computer science and mathematics dealing with the resources required during computation to solve a given problem Systems theory (or systemics or general systems theory): an interdisciplinary field including engineering, biology and philosophy that incorporates... Diagram of complexity classes provided that P ≠ NP. If P = NP, then all three classes are equal. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ...