Content deleted Content added
AmirOnWiki (talk | contribs) →Proof: minor fix of argument |
AmirOnWiki (talk | contribs) sharper hierarchy theorems |
||
Line 160:
However, the time hierarchy theorems provide no means to relate deterministic and non-deterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of [[computational complexity theory]]: whether [[P = NP problem|'''P''' and '''NP''']], '''NP''' and '''[[PSPACE]]''', '''PSPACE''' and '''EXPTIME''', or '''EXPTIME''' and '''NEXPTIME''' are equal or not.
==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--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 theory of Computing |date=1993 |pages=602-611 |doi=10.1145/167088.167244}}</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}}</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 ==
| |||