# Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

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

## 1 Answer

From the comment:

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

• What is $T^{-1}(DTM)$? – Emil Jeřábek Mar 28 '13 at 12:14
• $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. – Marzio De Biasi Mar 28 '13 at 13:23