Content deleted Content added
m Plural |
→Consequences: P does not collapse |
||
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''<sup>''k''</sup>) for some fixed ''k''. For example, there are problems solvable in O(''n''<sup>5000</sup>) time but not O(''n''<sup>4999</sup>) 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 would know 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.
| |||