Skip to main content
3 of 5
added 2 characters in body
Juho
  • 22.8k
  • 7
  • 62
  • 117

Are runtime bounds decidable for anything nontrivial?

Problem  Given a Turing machine M which has known runtime O(g(n)) with respect to input length n, is the runtime of MO(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

Chao Xu
  • 3.1k
  • 18
  • 34