Time hierarchy theorem
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, the run-time hierarchy of problems does not completely collapse. One theorem deals with deterministic computations and the other with non-deterministic ones.
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 2n.
Deterministic time hierarchy theorem
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 determininstic time f(n)2. In other words, the complexity class DTIME(f(n)) is a strict subset of DTIME(f(n)2).
The proof is not constructive and uses a diagonalization argument.
As a consequence, one can show that the class P is a strict subset of EXPTIME.
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)).
Referenced By
List of computability and complexity topics | List of mathematical logic topics | List of mathematical proofs | List of mathematical topics (S-U) | List of proofs
|
