Are runtime bounds in P decidable? (answer: no) The question asked is whether the following question is decidable:


  Problem&nbsp;&nbsp;Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect to input length $n$ ? 


A narrow answer of "yes", "no", or "open" is acceptable (with references, proof sketch, or a review of present knowledge), but broader answers too are very welcome.

Answer

Emanuele Viola has posted a proof  that the question is undecidable (see below).

Background

For me, this question arose naturally in parsing Luca Tevisan's answer to the question Do&nbsp;runtimes for P require EXP resources to upper-bound? … are concrete examples known?  

The question relates also to a MathOverflow question: What are the most attractive Turing undecidable problems in mathematics?, in a variation in which the word "mathematics" is changed to "engineering," in recognition that runtime estimation is an ubiquitous engineering problem associated to (for example) control theory and circuit design.

Thus, the&nbsp;broad objective in asking this question is to gain a better appreciation/intuition regarding which practical aspects of runtime estimation in the complexity class P are feasible (that is, require computational resources in P to estimate), versus&nbsp;infeasible (that is, require computational resources in EXP to estimate), versus formally&nbsp;undecidable.

---&nbsp;edit (post-answer)&nbsp;---

I have added Viola's theorem to MathOverflow's  community wiki "Attractive Turing-undecidable problems".  It&nbsp;is that&nbsp;wiki's first contribution associated to the complexity class&nbsp;P; this&nbsp;attests to the&nbsp;novelty, naturality, and broad scope of Viola's theorem (and IMHO its beauty too).

---&nbsp;edit (post-answer)&nbsp;---

Juris Hartmanis' monograph Feasible computations and provable complexity properties (1978) covers much of the same material as Emanuele Viola's proof.
The problem is undecidable. Specifically, you can reduce the halting problem to it as follows. Given an instance $(M,x)$ of the halting problem, construct a new machine $M&#39;$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for $n$ steps. If $M$ accepts, loop for $n^2$ steps and stop; otherwise loop for $n^3$ steps and stop.

If $M$ halts on $x$ it does so in $t=O(1)$ steps, so the run time of $M&#39;$ would be $O(n^2)$. If $M$ never halts then the run time of $M&#39;$ is at least $n^3$.

Hence you can decide if $M$ accepts $x$ by deciding if the run time of $M&#39;$ is $O(n^2)$ or $O(n^3)$.