Time hierarchy theorem: Difference between revisions

Revision as of 13:39, 29 September 2004

Revision as of 12:25, 4 October 2004

Line 47:

: <math> H_f \in \mathsf{TIME}(f(m)^3) </math>

It ishas possiblebeen toshown find[http://www.cs.berkeley.edu/~luca/cs172/noteh.pdf] that a provably more efficient model of simulation thatexists which establishes that

: <math> H_f \in \mathsf{TIME}(f(m) \left\lfloorlog f(m/2 \right\rfloor )^2) </math>

but since this model of simulation is rather involved, it is not included here.