12
$\begingroup$

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

Improve this question
$\endgroup$
4

1 Answer 1

Reset to default
12
$\begingroup$

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)$ ...

Improve this answer
$\endgroup$
2
  • 5
    $\begingroup$ What is $T^{-1}(DTM)$? $\endgroup$
    – Emil Jeřábek
    Mar 28, 2013 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, 2013 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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