patternMinor
Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?
Viewed 0 times
logbutexisttimethatdoesmachineturingthereruns
Problem
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)$?
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)$?
Solution
The answer seems to be negative, according to Corollary 4.12 of Verifying Time Complexity of Deterministic Turing Machines by David Gajser (ArXiv).
Context
StackExchange Computer Science Q#76294, answer score: 7
Revisions (0)
No revisions yet.