Time hierarchy theorem: Difference between revisions

Revision as of 18:50, 7 March 2024

Latest revision as of 19:58, 12 August 2025

(12 intermediate revisions by 8 users not shown)

Line 16:

| jstor = 1994208| doi-access = free

}}

</ref> It was improved a year later when F. C. Hennie and Richard E. Stearns improved the efficiency of the [[Universal Turing machine#Efficiency|Universaluniversal Turing machine]].<ref>{{cite journal

| last1 = Hennie

| first1 = F. C.

Line 98:

===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 ''o''(''f''(''n'')) but can be solved in worst-case deterministic time ''O''(''f''(''n'')log ''f''(''n'')). Thus

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

Equivalently, if <math>f, g</math> are time-constructable, and <math>f(n) \ln f(n) = o(g(n))</math>, then

<math display="block">\mathsf{DTIME}(f(n)) \subsetneq \mathsf{DTIME} (g(n))</math></blockquote>

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

'''Example.''' <math>\mathsf{DTIME}(n) \subsetneq \mathsf{DTIME} (n (\ln n)^2) </math>.

'''Example.''' There are problems solvable in time ''n''log²''n'' but not time ''n''. This follows by setting <math>f(n) = n\log n</math>, since ''n'' is in

:<math>o\left(n\log 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''(|''x''|) steps:

: <math> H_f = \left\{ ([M], x)\ |\ M \ \text{accepts}\ x \ \text{in}\ f(|x|) \ \text{steps} \right\}. </math>

Line 130 ⟶ 132:

:<math>\mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right). </math>

We use this ''K'' to construct another machine, ''N'', which takes a machine description [''M''] and runs ''K'' on the tuple ([''M''], [''M'']), ie. M is simulated on its own code by ''K'', and then ''N'' accepts if ''K'' rejects, and rejects if ''K'' accepts.

If ''n'' is the length of the input to ''N'', then ''m'' (the length of the input to ''K'') is twice ''n'' plus some delimiter symbol, so ''m'' = 2''n'' + 1. ''N'''s running time is thus

:<math> \mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right) = \mathsf{TIME}\left(f\left( \left\lfloor \frac{2n+1}{2} \right\rfloor \right)\right) = \mathsf{TIME}\left(f(n)\right). </math>

Now if we feed [''N''] as input into ''N'' itself (which makes ''n<nowiki/>'' the length of [''N'']) and ask the question whether ''N'' accepts its own''N''' description as input, we get:

* If ''N'' accepts' [''acceptsN'<nowiki/>'' [''N'<nowiki/>''' ] (which we know it does in at most ''f''(''n'') operations since ''K'' halts on ([''N'' ], [''N'<nowiki/>'''''<nowiki/>''']) in ''f''(''n'') steps), this means that ''K'' '''rejects''' ([''N'<nowiki/>''], [''N'<nowiki/>'']), so ([''N''], [''N'<nowiki/>'']) is not in ''H_f'', and so by the definition of ''H_f'', this implies that ''N'' does not accept [''N'<nowiki/>''] in ''f''(''n'') steps. Contradiction.

* If ''N'' '''rejects''' [''N'<nowiki/>''] (which we know it does in at most ''f''(''n'') operations), this means that ''K'' '''accepts''' ([''N'<nowiki/>''], [''N'<nowiki/>'''''<nowiki/>''']), so ([''N'' ], [''N'<nowiki/>'']) '''is''' in ''H_f'', and thus ''N'' '''does''' accept [''N'<nowiki/>''] in ''f''(''n'') steps. Contradiction.

We thus conclude that the machine ''K'' does not exist, and so

Line 166 ⟶ 169:

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–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 journalbook |last1=Jones |first1=Neil D. |title=ConstantProceedings factorsof ''do''the mattertwenty-fifth |journal=25thannual SymposiumACM symposium on the Theory of Computingcomputing - STOC '93 |chapter=Constant time factors ''do'' matter |date=1993 |pages=602–611 |doi=10.1145/167088.167244|isbn=0-89791-591-7 |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=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==