Time hierarchy theorem: Difference between revisions

Revision as of 20:04, 8 September 2008

Revision as of 03:12, 17 September 2008

Line 1:

In [[computational complexity theory]], the '''time hierarchy theorems''' are important statements proven by [[Juris Hartmanis]] that ensure the existence of certain "hard" problems which cannot be solved in a given amount of time. As a consequence, for every time-bounded [[complexity class]], there is a strictly larger time-bounded complexity class, and so the run-time hierarchy of problems does not completely collapse. One theorem deals with deterministic computations and the other with non-deterministic ones. The analogous theorems for space are the [[space hierarchy theorem]]s.

== Background ==