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:
“Every expansion of government in business means that government in order to protect itself from the political consequences of its errors and wrongs is driven irresistibly without peace to greater and greater control of the nation’s press and platform. Free speech does not live many hours after free industry and free commerce die.”
—Herbert Hoover (1874–1964)
“Without being forgiven, released from the consequences of what we have done, our capacity to act would ... be confined to one single deed from which we could never recover; we would remain the victims of its consequences forever, not unlike the sorcerer’s apprentice who lacked the magic formula to break the spell.”
—Hannah Arendt (1906–1975)
“The middle years are ones in which children increasingly face conflicts on their own,... One of the truths to be faced by parents during this period is that they cannot do the work of living and relating for their children. They can be sounding boards and they can probe with the children the consequences of alternative actions.”
—Dorothy H. Cohen (20th century)