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:
“We are still barely conscious of how harmful it is to treat children in a degrading manner. Treating them with respect and recognizing the consequences of their being humiliated are by no means intellectual matters; otherwise, their importance would long since have been generally recognized.”
—Alice Miller (20th century)
“Resistance is feasible even for those who are not heroes by nature, and it is an obligation, I believe, for those who fear the consequences and detest the reality of the attempt to impose American hegemony.”
—Noam Chomsky (b. 1928)
“There is a delicate balance of putting yourself last and not being a doormat and thinking of yourself first and not coming off as selfish, arrogant, or bossy. We spend the majority of our lives attempting to perfect this balance. When we are successful, we have many close, healthy relationships. When we are unsuccessful, we suffer the natural consequences of damaged and sometimes broken relationships. Children are just beginning their journey on this important life lesson.”
—Cindy L. Teachey. “Building Lifelong Relationships—School Age Programs at Work,” Child Care Exchange (January 1994)