Return to Question

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

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

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)][1]. One can derive from [Viola's answer][2] 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$.

One of the interesting questions would be for arbitrary $g(n)$ and $f(n)=1$. [1]: http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no [2]: http://cstheory.stackexchange.com/a/5006/314

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

Problem  Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M$ ${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)][1]. One can derive from [Viola's answer][2] 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$.

One of the interesting questions would be for arbitrary $g(n)$ and $f(n)=1$. [1]: http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no [2]: http://cstheory.stackexchange.com/a/5006/314

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)][1]. One can derive from [Viola's answer][2] 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$.

One of the interesting questions would be for arbitrary $g(n)$ and $f(n)=1$. [1]: http://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no [2]: http://cstheory.stackexchange.com/a/5006/314