Time hierarchy theorem: Difference between revisions

Revision as of 12:37, 9 February 2007

Revision as of 11:50, 31 July 2007

Line 70:

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

== References ==