Content deleted Content added
Add statement that similar theorems are not known for probabilistic time or for quantum time (reference is from Rudich complexity book, don't have it with me) |
+proof overview |
||
Line 1:
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 theorem]]s.
== Background ==
Both theorems use the notion of a [[constructible function|time-constructible function]]. A [[function (mathematics)|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 [[polynomial]]s with non-negative integral coefficients are time-constructible, as are exponential functions such as 2<sup>''n''</sup>.
== 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 ==
| |||