# 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

• 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)$ Mar 27, 2013 at 23:03
• Nice, seems to be just what I was looking for. Do you want to convert it into an answer? Mar 28, 2013 at 10:16
• interesting question but object to the redefinition of a standard complexity class DTIME in a nonstandard way, suggest you at least call it something like DTIME' to avoid confusion
– vzn
Sep 5, 2013 at 17:44
• This paper maybe helpful. [Rosenberg 67] Real-Time Definable Languages dl.acm.org/citation.cfm?id=321423 Oct 25, 2013 at 2:14

... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...
• What is $T^{-1}(DTM)$? Mar 28, 2013 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. Mar 28, 2013 at 13:23