Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice that there is no $O(\cdot)$ around $f(n) + 1$.

Is it true that $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

Using the linear speed-up theorem, we can prove $\mathsf{DTIME}(2n) = \mathsf{DTIME}(1.01n)$, but can we reach $n$?

It seems that the language of palindromes is in $\mathsf{DTIME}(n)$; for related topics, see Lipton's blog post about string algorithms


From the comment:

In "Deterministic Turing Machines in the Range between Real-Time and Linear-Time" I found:

... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...

  • 5
    $\begingroup$ What is $T^{-1}(DTM)$? $\endgroup$ – Emil Jeřábek Mar 28 '13 at 12:14
  • 1
    $\begingroup$ $T^{-1}(DTM)$ is the inverse of an increasing, unbounded time-constructible function $f$ ( $\forall c \in \mathbb{N}, \exists n_0, c' \in \mathbb{N}$ s.t $\forall n \geq n_0$ we have $c f(n) \leq f(c'n)$ ). You can replace it with a honest sublinear function. $\endgroup$ – Marzio De Biasi Mar 28 '13 at 13:23

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.