Time hierarchy theorem: Difference between revisions

Revision as of 19:00, 29 May 2005

Revision as of 20:56, 25 June 2005

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 equivalent theorem for space is the [[space hierarchy theorem]].

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^''n''.

Line 7:

===Statement===

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 deterministic time ''f''(''n'')². In other words, the complexity class [[DTIME|TIME]](''f''(''n'')) is a strict subset of TIMEDTIME(''f''(''n'')²).

Even more generally, it can be shown that if ''f''(''n'')log ''f''(''n'') grows slower asymptotically than ''g''(''n''), then more problems can be solved in deterministic time ''g''(''n'') than in time ''f''(''n'').[http://www.cs.ubc.ca/~condon/cpsc506/lectures/lec2.pdf] For example, there are problems solvable in time ''n''² but not time ''n'', since ''n'' log ''n'' grows slower asymptotically than ''n''².

===Proof===

We include here a proof that TIMEDTIME(''f''(''n'')) is a strict subset of TIMEDTIME(''f''(2''n'' + 1)³) as it is simpler. See the bottom of this section for information on how to extend the proof to ''f''(''n'')².

To prove this, we first define a language as follows:

Line 55 ⟶ 57:

==Consequences==

The time hierarchy theorems guarantee that the deterministic and non-deterministic version of the [[exponential hierarchy]] are genuine hierarchies: in other words [[Complexity classes P and NP(complexity)|P]] ⊂ [[EXPTIME]] ⊂ 2-EXP ⊂ ..., and [[NP (complexity)|NP]] ⊂ [[NEXPTIME]] ⊂ 2-NEXP ⊂ ...

The theorem also guarantees that there are problems in the '''P''' requiring arbitrarily large exponents to solve. 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.

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 [[Complexity classes P and NP|P and NP]], NP and [[PSPACE]], PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not.