Consequences
The time hierarchy theorems guarantee that the deterministic and non-deterministic versions of the exponential hierarchy are genuine hierarchies: in other words P ⊂ EXPTIME ⊂ 2-EXP ⊂ ... and NP ⊂ NEXPTIME ⊂ 2-NEXP ⊂ ....
For example, P ⊂ EXPTIME since P ⊆ DTIME(2n) ⊂ DTIME(22n) ⊆ EXPTIME.
The theorem also guarantees that there are problems in P requiring arbitrary large exponents to solve; in other words, P does not collapse to DTIME(nk) for any fixed k. For example, there are problems solvable in n5000 time but not n4999 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 and NP, NP and PSPACE, PSPACE and EXPTIME, or EXPTIME and NEXPTIME are equal or not.
Read more about this topic: Time Hierarchy Theorem
Famous quotes containing the word consequences:
“The consequences of our actions grab us by the scruff of our necks, quite indifferent to our claim that we have “gotten better” in the meantime.”
—Friedrich Nietzsche (1844–1900)
“[As teenager], the trauma of near-misses and almost- consequences usually brings us to our senses. We finally come down someplace between our parents’ safety advice, which underestimates our ability, and our own unreasonable disregard for safety, which is our childlike wish for invulnerability. Our definition of acceptable risk becomes a product of our own experience.”
—Roger Gould (20th century)
“War is thus divine in itself, since it is a law of the world. War is divine through its consequences of a supernatural nature which are as much general as particular.... War is divine in the mysterious glory that surrounds it and in the no less inexplicable attraction that draws us to it.... War is divine by the manner in which it breaks out.”
—Joseph De Maistre (1753–1821)