Time hierarchy theorem: Difference between revisions

Revision as of 18:50, 7 March 2024

Revision as of 08:18, 10 July 2024

Line 169:

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=39–44|doi=10.1016/S0020-0190(03)00253-9 }}</ref> that, in the above movelsmodels, 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==