Vipul: Created page with "==Statement== ===Existential version=== Suppose $f$ is a time-constructible function. Then, there exists a deterministic time complexity class that is strict..."

2011-12-28T02:35:05Z

Created page with "==Statement== ===Existential version=== Suppose <math>f</math> is a time-constructible function. Then, there exists a deterministic time complexity class that is strict..."

New page

==Statement==

===Existential version===

Suppose <math>f</math> is a [[time-constructible function]]. Then, there exists a [[deterministic time complexity class]] that is strictly larger than <math>DTIME(f(n))</math>. The explicit description of this depends on the choice of model of computation that we are using to define <math>DTIME</math>.

===Explicit version===

With a suitable model of computation, we can show that <math>DTIME(f(n))</math> is strictly contained in <math>DTIME(f(n) \log f(n))</math>.

==Proof==

The key idea behind the proof is the [[diagonalization argument]].

Deterministic time hierarchy theorem - Revision history

Vipul: Created page with "==Statement== ===Existential version=== Suppose f is a time-constructible function. Then, there exists a deterministic time complexity class that is strict..."

Vipul: Created page with "==Statement== ===Existential version=== Suppose $f$ is a time-constructible function. Then, there exists a deterministic time complexity class that is strict..."