Time hierarchy theorem: Difference between revisions

Revision as of 17:39, 29 June 2023

Revision as of 13:40, 30 June 2023

Line 93:

===Statement===

<blockquote>'''Time Hierarchy Theorem.''' If ''f''(''n'') is a time-constructible function, then there exists a [[decision problem]] which cannot be solved in worst-case deterministic time ''f''(''n'') but can be solved in worst-case deterministic time asymptotically bigger than ''f''(''n'')².log In''f''(''n''). otherFor wordsinstance,

:<math>\mathsf{DTIME}(f(n)) \subsetneq \mathsf{DTIME}\left (f(n)\log^2 f(n) \right).</math></blockquote>

'''Note 1.''' ''f''(''n'') is at least ''n'', since smaller functions are never time-constructible.<br>

'''Note 2.''' EvenThe moreprecise generally,statement itof the algorithm can be shownwritten using [[little o|little o notation]] as thatfollows: if ''f''(''n'') is time-constructible, then

:<math>\mathsf{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right)\subsetneq \mathsf{DTIME}\left (f(n) \right).</math>

For example, there are problems solvable in time ''n''log²''n'' but not time ''n'', since ''n'' is in

:<math>o\left(\frac{n\log^2 n}{\log {(n\log^2 n)}}\right).</math>

===Proof===

We include here a proof of a weaker result, namely that '''DTIME'''(''f''(''n'')) is a strict subset of '''DTIME'''(''f''(2''n'' + 1)³), as it is simpler but illustrates the proof idea. See the bottom of this section for information on how to extend the proof to ''f''(''n'')²log''f''(''n'').

To prove this, we first define the language of the encodings of machines and their inputs which cause them to halt within f

Line 143:

===Extension===

The reader may have realised that the proof isgives simplerthe weaker result because we have chosen a simple Turing machine simulation for which we can be certainknow that

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

It hasis been shownknown<ref>Luca{{cite Trevisan,book [http://www.cs.berkeley.edu/~luca/cs172/noteh.pdf|last1=Sipser Notes|first1=Michael on|title=Introduction Hierarchyto Theorems],the U.C.Theory Berkeleyof Computation |publisher=CENGAGE learning |isbn=1-133-18779-X |edition=3rd}}</ref> that a more efficient model of simulation exists which establishes that

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

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

Observe however that an identical argument as above then implies that <math>DTIME(r(f(2m+1)))</math> is not contained within <math>DTIME(f(m))</math> if <math>r(f(|M|+|x|))</math> is a function which gives a time within which it is possible to simulate a machine <math>M</math> with time complexity <math>f(n)</math> on input <math>x</math>.

==Non-deterministic time hierarchy theorem==