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)∈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)∉o(n) and f(n)∉O(g(n)) then the problem is undecidable.
The requirement that f(n)∉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