Time hierarchy theorem: Difference between revisions

Revision as of 13:06, 18 May 2004

Revision as of 12:33, 1 June 2004

Line 1:

[[Category: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.