7
$\begingroup$

It is known that any (deterministic, single-taped) Turing-machine that runs in time $o(n\log n)$, decides a regular language (e.g., see this link). Thus, there exists an equivalent Turing-machine that runs in time $O(n)$. In other words, if $t(n)=o(n\log n)$ then $$\mathsf{DTIME}\left(t\left(n\right)\right)\backslash\mathsf{DTIME}\left(n\right)=\emptyset.$$

I was wondering whether there exists an example in which the original Turing-machine was not already running in time $O(n)$.

To sum up: Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?

Improve this question
$\endgroup$
2
  • $\begingroup$ You can make a Turing machine run in $O(n \log \log n)$ if you'd like to. However, do you need it to decide a regular language? $\endgroup$
    – Pål GD
    Jun 4, 2017 at 13:33
  • 1
    $\begingroup$ @PålGD Sure, that's trivial. Do you mean $\Theta(n\log\log n)$? And is it a single-tape machine? $\endgroup$
    – David Richerby
    Jun 4, 2017 at 15:59

1 Answer 1

Reset to default
7
$\begingroup$

The answer seems to be negative, according to Corollary 4.12 of Verifying Time Complexity of Deterministic Turing Machines by David Gajser (ArXiv).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.