Editing Time hierarchy theorem (section)

==Consequences==
The time hierarchy theorems guarantee that the deterministic and non-deterministic versions of the [[exponential hierarchy]] are genuine hierarchies: in other words '''[[P (complexity)|P]]''' ⊊ '''[[EXPTIME]]''' ⊊ '''[[2-EXP]]''' ⊊ ... and '''[[NP (complexity)|NP]]''' ⊊ '''[[NEXPTIME]]''' ⊊ '''2-NEXP''' ⊊ ....

For example, <math>\mathsf{P} \subsetneq \mathsf{EXPTIME}</math> since <math>\mathsf{P} \subseteq \mathsf{DTIME} (2^n)\subsetneq  \mathsf{DTIME} (2^{2n}) \subseteq \mathsf{EXPTIME}</math>. Indeed, <math>\mathsf{DTIME}\left(2^n\right) \subseteq \mathsf{DTIME}\left(o\left(\frac{2^{2n}}{2n}\right)\right) \subsetneq \mathsf{DTIME}(2^{2n})</math> from the time hierarchy theorem.

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''<sup>''k''</sup>) for any fixed ''k''. For example, there are problems solvable in ''n''<sup>5000</sup> time but not ''n''<sup>4999</sup> time. This is one argument against [[Cobham's thesis]], the convention that '''P''' is a practical class of algorithms. 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 [[computational complexity theory]]: whether [[P = NP problem|'''P''' and '''NP''']], '''NP''' and '''[[PSPACE]]''', '''PSPACE''' and '''EXPTIME''', or '''EXPTIME''' and '''NEXPTIME''' are equal or not.