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.



Your Answer

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