Problem  Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$?

Is the above problem decidable for some nontrivial pairs of $g$ and $f$?A solution is trivial if $g(n) \in O(f(n))$.

This is related to the problem Are runtime bounds in P decidable? (answer: no). One can derive from Viola's answer that if $f(n)\not \in o(n)$ and $f(n)\not \in O(g(n))$ then the problem is undecidable.

The requirement that $f(n)\not \in o(n)$ is because the $M'$ in Viola's proof need $O(n)$ time to find its input size. Thus Viola's proof could not work when $f(n)=1$.

It would be interesting if we can decide on the run time of sublinear time algorithms. A special case is when we have arbitrary $g(n)$ and $f(n)=1$.

  • $\begingroup$ Since the question you link to was very well received on CSTheory, you might want to flag for migration later. $\endgroup$
    – Juho
    Jun 9 '13 at 14:06

Here are a few remarks which could be relevant:

  1. Kobayashi proved that a TM running in time $o(n\log n)$ accepts a regular language (and so runs in time $O(n)$); recently this has been extended to non-deterministic TMs (Tadaki, Yamakami and Lin).
  2. Machines running in time $o(n)$ actually run in constant time (consider any $n$ for which the running time is less than $n$; adding characters to the end doesn't affect the TM).
  • 1
    $\begingroup$ it is worth pointing out that 1. holds for one-tape TMs only $\endgroup$ Jun 9 '13 at 6:29

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.