Time hierarchy theorem: Difference between revisions

Revision as of 20:50, 26 June 2005

Revision as of 11:08, 28 June 2005

Line 7:

===Statement===

If ''f''(''n'') is a time-constructible function and is at least ''n'', 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]](''f''(''n'')) is a strict subset of DTIME(''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''².

Line 59:

The time hierarchy theorems guarantee that the deterministic and non-deterministic version of the [[exponential hierarchy]] are genuine hierarchies: in other words [[P (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; in other words, '''P''' does not collapse to DTIME(''n''^''k'') for someany 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 wouldcould knowdeduce 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 [[Complexity classes P and NP|P and NP]], NP and [[PSPACE]], PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not.