Time hierarchy theorem: Difference between revisions

Revision as of 19:36, 3 March 2004

Revision as of 19:38, 3 March 2004

Line 54:

As a consequence, one can show that the class [[Complexity classes P and NP|'''P''']] is a strict subset of [[EXPTIME]], which is defined as:

: <math> \mathsf{EXPEXPTIME} = \bigcup_{k=1}^\infty \mathsf{TIME} (2^{n^k}) </math>

== Non-deterministic time hierarchy theorem ==