Revision as of 12:25, 4 October 2004 edit Timwi (talk \| contribs) Administrators 32,166 edits →Extension: Include the information from the talk page ← Previous edit		Revision as of 08:15, 20 November 2004 edit undo Dcoetzee (talk \| contribs) 37,529 edits Categories to end Next edit →
Line 1: [[Category:Computational complexity theory]][[Category:Theorems]]▼ In [[computational complexity theory]], the '''time hierarchy theorems''' are important statements that ensure the existence of certain "hard" problems which cannot be solved in a given amount of time. As a consequence, the run-time hierarchy of problems does not completely collapse. One theorem deals with deterministic computations and the other with non-deterministic ones. Line 60 ⟶ 58: 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. ▲[[Category:Computational complexity theory]][[Category:Theorems]]

Time hierarchy theorem: Difference between revisions