6
$\begingroup$

The time hierarchy for multitape Turing machines is tight (see [1]): if $f(n)=o(g(n))$ and $f,g$ are well-behaved, then $\textrm{DTIME}(f(n))\subsetneq \textrm{DTIME}(g(n))$. However, for one-tape Turing machines there is a logarithmic gap: if $f(n)=o(g(n)/\log g(n))$, then $\textrm{DTIME}_1(f(n))\subsetneq \textrm{DTIME}_1(g(n))$. I am wondering how tight is this result. It is known that there are no time complexity classes between $\textrm{DTIME}_1(n)$ and $\textrm{DTIME}_1(n\log n)$. But what happens for time functions greater than $n\log n$?

Question. Are there complexity classes strictly between $\textrm{DTIME}_1(n\log n)$ and $\textrm{DTIME}_1(n(\log n)^2)$?

[1] M. Fürer, The Tight Deterministic Time Hierarchy, 1982.

Improve this question
$\endgroup$

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.