Time hierarchy theorem: Difference between revisions

Revision as of 01:45, 10 July 2023

Revision as of 18:28, 3 August 2023

Line 146:

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

It is known<ref>{{cite book |last1=Sipser |first1=Michael |title=Introduction to the Theory of Computation |date=27 June 2012 |publisher=CENGAGE learning |isbn=978-1-133-18779-X0 |edition=3rd}}</ref> that a more efficient simulation exists which establishes that

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

Line 163:

==Sharper hierarchy theorems==

The gap of approximately <math>\log f(n)</math> between the lower and upper time bound in the hierarchy theorem can be traced to the efficiency of the device used in the proof, namely a universal program that maintains a step-count. This can be done more efficiently on certain computational models. The sharpest results, presented below, have been proved for:

* The unit-cost [[random access machine]]<ref>{{cite journal |last1=Sudborough |first1=Ivan H. |last2=Zalcberg |first2=A. |title=On Families of Languages Defined by Time-Bounded Random Access Machines |journal=SIAM Journal on Computing |date=1976 |volume=5 |issue=2 |pages=217--230217–230 |doi=10.1137/0205018}}</ref>

* A [[programming language]] model whose programs operate on a binary tree that is always accessed via its root. This model, introduced by [[Neil D. Jones]]<ref>{{cite journal |last1=Jones |first1=Neil D. |title=Constant factors ''do'' matter |journal=25th Symposium on the theoryTheory of Computing |date=1993 |pages=602-611602–611 |doi=10.1145/167088.167244|s2cid=7527905 }}</ref> is stronger than a deterministic Turing machine but weaker than a random access machine.

For these models, the theorem has the following form:

<blockquote>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 time ''af''(''n'') for some constant ''a'' (dependent on ''f'').</blockquote>

Thus, a constant-factor increase in the time bound allows for solving more problems, in contrast with the situation for Turing machines (see [[Linear speedup theorem]]). Moreover, Ben-Amram proved<ref>{{cite journal |last1=Ben-Amram |first1=Amir M. |title=Tighter constant-factor time hierarchies |journal=Information Processing Letters |date=2003 |volume=87 |issue=1 |pages=3939–44|doi=10.1016/S0020-440190(03)00253-9 }}</ref> that, in the above movels, for ''f'' of polynomial growth rate (but more than linear), it is the case that for all <math>\varepsilon > 0</math>, there exists a decision problem which cannot be solved in worst-case deterministic time ''f''(''n'') but can be solved in worst-case time <math>(1+\varepsilon)f(n)</math>.

== See also ==