Informally, these theorems say that given more time, a Turing machine can solve more problems.
The time hierarchy theorem for deterministic multi-tape Turing machines was first proven by Richard E. Stearns and Juris Hartmanis in 1965.
More precisely, the time hierarchy theorem for deterministic Turing machines states that for all time-constructible functions 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.
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.
, 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 2n.
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)).
To prove this, we first define the language of the encodings of machines and their inputs which cause them to halt within f Notice here that this is a time-class.
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 Hf by way of a deterministic Turing machine R, that simulates M for f(x) steps by first calculating f(|x|) and then writing out a row of 0s of that length, and then using this row of 0s as a "clock" or "counter" to simulate M for at most that many steps.
on a multitape machine, where |M| is the length of the encoding of M), we have that: The rest of the proof will show that so that if we substitute 2n + 1 for m, we get the desired result.
Let us assume that Hf is in this time complexity class, and we will reach a contradiction.
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: We thus conclude that the machine K does not exist, and so The reader may have realised that the proof gives the weaker result because we have chosen a simple Turing machine simulation for which we know that It is known[7] that a more efficient simulation exists which establishes that 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).
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(nk) for any fixed k. For example, there are problems solvable in n5000 time but not n4999 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.
between the lower and upper time bound in the hierarchy theorem can be traced to the efficiency of the device used in the proof, namely a universal program that maintains a step-count.
The sharpest results, presented below, have been proved for: For these models, the theorem has the following form: If f(n) is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic time f(n) but can be solved in worst-case time af(n) for some constant a (dependent on f).Thus, a constant-factor increase in the time bound allows for solving more problems, in contrast with the situation for Turing machines (see Linear speedup theorem).
Moreover, Ben-Amram proved[10] that, in the above models, for f of polynomial growth rate (but more than linear), it is the case that for all