Time hierarchy theorem: Difference between revisions

Revision as of 16:24, 24 May 2006

Revision as of 23:19, 30 August 2006

Line 10:

== Deterministic time hierarchy theorem ==

===Statement===

Line 67 ⟶ 66:

==Consequences==

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 '''P''' requiring arbitrarily large exponents to solve; in other words, '''P''' does not collapse to DTIME(''n''^''k'') for any 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 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 [[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.

Line 77 ⟶ 76:

* [[Stephen Cook]] (1972). [http://portal.acm.org/citation.cfm?id=804913 A hierarchy for nondeterministic time complexity]. ''Proceedings of the fourth annual ACM symposium on Theory of computing'', pp.187–192.

* {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Pages 310–313 of section 9.1: Hierarchy theorems.

* {{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | id = ISBN 02015308210-201-53082-1}} Section 7.2: The Hierarchy Theorem, pp.143–146.

[[Category:Computational complexity theory]]
[[Category:Mathematical theorems]]