<p><em>This is a rephrasing of Emanuele Viola's answer with the goal to be more understandable.</em></p>

<p>We show that the given problem $P$ is undecidable by reducing the general halting problem $H$ to it.</p>

<p>Let $(M, x)$ be any instance of the halting problem, that is we have to decide wether $M(x)\downarrow$ ($M$ halts on $x$). Construct a Turing machine $M^*$ that works as follows:</p>

<pre><code>M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}
</code></pre>

<p>Now we observe the following implications:</p>

<p>$\begin{align*} 
  M(x) \downarrow \quad &amp;\Rightarrow \exists n_0 \in \mathbb{N} : M \text{ halts on } x \text{ after at most } n_0 \text{ steps} \\
  &amp;\Rightarrow \forall y : n \geq n_0 \Rightarrow M^*(y) \text{ executes } n^2 \text{ arbitrary steps} \\
  &amp;\Rightarrow T_{M^*}(n) \in \mathcal{O}(n^2)
\end{align*}$</p>

<p>and</p>

<p>$\begin{align*} 
  M(x) \uparrow \quad &amp;\Rightarrow \forall n \in \mathbb{N} : M \text{ does not halt on } x \text{ in less than } n \text{ steps} \\
  &amp;\Rightarrow \forall y :  M^*(y) \text{ executes } n^3 \text{ arbitrary steps} \\
  &amp;\Rightarrow T_{M^*}(n) \in \Omega(n^3)
\end{align*}$</p>

<p>Therefore, $H(M,x) \Leftrightarrow P(M^*,2)$. Assuming $P$ was algorithmicaly decidable, so would be $H$, which yields a contradiction. $\square$</p>

CC BY-SA 3.0
2011-02-19T00:36:05.173Z
2011-07-05T19:14:18.320Z
2011-07-05T19:14:18.320Z
Raphael
<p>On the positive side, it is decidable whether a one-tape Turing machine runs in time $n \mapsto C \cdot n + D$ for given $C, D \in \mathbb{N}$, see:</p>

<blockquote>
  <p>David Gajser: <em>Verifying whether One-Tape Non-Deterministic Turing Machines Run in Time $Cn+D$</em>, <a href="http://arxiv.org/abs/1312.0496">arXiv:1312.0496</a></p>
</blockquote>

CC BY-SA 3.0
2015-05-03T21:56:56.227Z
No shortage of unusual behavior by small-time one-tape TMs. :)
Kaveh
CC BY-SA 3.0
2015-05-03T16:43:39.670Z
2015-05-03T16:43:39.670Z
Andrej Bauer
<p>The problem was also solved in my article "<a href="http://dl.acm.org/citation.cfm?id=1328455" rel="nofollow noreferrer">The intensional content of Rice's Theorem</a>" POPL'2008, where I prove that no "complexity clique" is decidable. 
A complexity clique is a class of programs closed w.r.t. programs with similar behavior <em>and</em> complexity. I also provides necessary conditions for semi-decidable properties. </p>

<p>Programs running in O(n^k) are a complexity clique in the above sense, hence the set is not decidable.</p>

<p>The result has also been recently extended to subrecursive settings (such as P) by Mathieu Hoyrup: <a href="https://hal.inria.fr/hal-01308224/" rel="nofollow noreferrer">The decidable properties of subrecursive functions</a> (ICALP 2016).</p>

CC BY-SA 3.0
2017-02-14T11:58:43.703Z
2017-02-15T15:20:53.153Z
2017-02-15T15:20:53.153Z
Andrea Asperti
<p>To add to the previous answers, this problem is not only undecidable but $Σ^0_2$ complete.  Thus, it is undecidable even if the decider has an oracle for the halting problem.  </p>

<p>To clarify the completeness, while the P-time promise condition is also $Σ^0_2$-complete, there is a decidable set of codes $S$ such that all machines in $S$ are polynomial time and the $O(n^2)$ question is $Σ^0_2$ complete on $S$.</p>

<p>To prove this, choose a $Σ^0_2$ complete $φ$, $φ(x) ⇔ ∃k ∀m \, ψ(x,k,m)$ with $ψ$ polynomial time computable (for binary numbers).</p>

<p>Then $φ(x)$ holds iff the following machine is $O(n^2)$ where $n$ is the input length (the machine only cares about the input length):</p>

<p>for $k$ in 0 to $n$:<br/>
&nbsp;&nbsp;&nbsp; if $∀m&lt;n \, ψ(x,k,m)$: # tested using a loop<br/>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; halt<br/>
&nbsp;&nbsp;&nbsp; wait for $n^2$ steps<br/>
halt</p>

<p>Note that for every not-too-small $c$, whether a program always halts in (for example) $≤n^2+c$ steps is $Π^0_1$-complete, but asking about bounds in a robust manner gives $Σ^0_2$-completeness.</p>

CC BY-SA 3.0
2017-09-14T19:54:05.383Z
2017-09-14T19:54:05.383Z
Dmytro Taranovsky
<h1>Not even possible with a halting oracle</h1>
<p>Consider function</p>
<pre><code>p=0, r=[halted]
for input:
    if r=[halted]:
        p=p+1
        r=Program Q with input p
    Step r once
wait p
</code></pre>
<p>Here &quot;wait&quot; loops for <span class="math-container">$p \cdot input^h$</span> times so the <code>for</code> before can be ignored</p>
<p>Here <code>p</code> in bounded and time complexity in <span class="math-container">$O(input^h)$</span> iff Q(p) doesn't halt, which is <span class="math-container">$\sum_2$</span></p>
<hr />
<p>Also, this question is in <span class="math-container">$\sum_2$</span>: Exist a <span class="math-container">$p$</span>, s.t. for each input <span class="math-container">$n$</span>, P runs in <span class="math-container">$p\cdot n^k$</span> time</p>

CC BY-SA 4.0
2022-12-29T18:26:40.597Z
2022-12-29T18:26:40.597Z
l4m2
<p>Here is a proof that to me seems better than the one by Mr Viola in that it does not seemingly abstractly suppose some undecidable sentence.</p>
<p>Theorem. There is no machine R such that R(&lt;M,k&gt;)=1 iff M runs within time O(n^k) given that M is promised to be in P.</p>
<p>Proof.</p>
<p>Fix k to be some value and we obtain the algorithm R(.) which takes as its argument the encoding of a machine only (promised to be in P) and outputs 1 if and only if it runs within time O(n^k). Let the language it decides be denoted R(k)
Construct R* as follows.
If R outputs 1 on the code R*, then loop for time n^(k+1),
otherwise, loop for time n^k,
halt.</p>
<p>Now run R on R*. This machine encoding is in the set R(k) iff it is not in the set R(k) a contradiction.</p>
<p>Hence, neither R* nor R can exist.</p>
<p>Observe that this is essentially the proof of Rice's Theorem. Observe that we can construct such diagonal arguments for such algorithmically definable properties of Turing machines (modulo some subtleties at the boundaries).</p>

CC BY-SA 4.0
2021-09-02T05:52:35.927Z
2021-10-01T05:18:22.680Z
2021-10-01T05:18:22.680Z
Z_22
<p>here is recent new more systematic analysis/ angles/ results on this question &amp; related ones, introducing the concept of "algorithmic verifiability" and a Rice-like-thm analog for complexity theory. one relevant section from the abstract is follows and there are many other related theorems related to provability of P vs NP etc</p>

<ul>
<li><p><a href="http://eccc.hpi-web.de/report/2015/159/" rel="nofollow">Why the Concept of Computational Complexity is Hard for Verifiable Mathematics</a> / Hromkovic</p>

<blockquote>
  <p>First, we prove Rice's theorem for unprovability, claiming that each nontrivial semantic problem about programs is not almost everywhere solvable in Algorithmically Verifiable "AV"-mathematics. Using this, we show that there are infinitely many algorithms (programs that are provably algorithms) for which there do not exist proofs that they work in polynomial time or that they do not work in polynomial time. ...</p>
  
  <p>Note that, if P != NP is provable in AV-mathematics, then for each algorithm A it is provable that "A does not solve SATISFIABILITY or A does not work in polynomial time". Interestingly, we finally show that there exist algorithms for which it is neither provable that they do not work in polynomial time, nor that they do not solve SATISFIABILITY. Moreover, there is an algorithm solving SATISFIABILITY for which one cannot prove in AV-mathematics that it does not work in polynomial time.</p>
  
  <p>Furthermore, we show that P = NP implies the existence of algorithms X for which the claim "X solves SATISFIABILITY in polynomial time" is not provable in AV-mathematics.</p>
</blockquote></li>
</ul>

CC BY-SA 3.0
2015-09-29T18:09:00.930Z
2015-09-29T18:09:00.930Z
vzn
<p>The solution from Viola can be generalized to any running time (beyond poly): You can reduce the halting problem to it as follows. Given an instance (M,x) of the halting problem, construct a new machine M′ that works as follows: on inputs of length n, it simulates M on x for f(n) steps or until M halts, where f(n) is any arbitrary increasing function (greater than constant) of n. (Obs.: M′ reads gradually the input, in order to avoid wasting linear time [O(n)] just to read needlessly all the input, if it is large enough and M halts.)</p>

<p>If M halts on x it does so in T=O(1) steps, so the run time of M′ would be O(1). If M never halts then the run time of M′ is O(n^2*f(n)).</p>

<p>Hence you can decide if M accepts x by deciding if the run time of M′ is O(1) or O(n^2*f(n)).</p>

<p>Then, the auxiliary code from Raphael can be generalized accordingly by:</p>

<p>Let (M,x) be any instance of the Halting Problem, that is we have to decide whether M halts on x. Construct a deterministic Turing Machine (DTM) M* that works as follows:</p>

<ol>
<li>M*(input) = {</li>
<li>n := 0</li>
<li>Read the first symbol from the input</li>
<li>Loop: </li>
<li>n := n+1</li>
<li>Simulate M(x) for f(n) steps or until M(x) halts</li>
<li>Read the next symbol from the input</li>
<li>Loop until end_of_input or until M(x) has halted</li>
<li>}</li>
</ol>

<p>Now we observe the following implications:</p>

<p>M halts on x after at most k (constant) steps => T(M*) = O(1) and</p>

<p>M never halts on x => T(M*) = O(n^2*f(n))</p>

<p>Therefore, even deciding whether the running time of an arbitrary DTM is simply greater than constant is as hard as Halting Problem. □</p>

CC BY-SA 3.0
2011-05-18T20:49:54.083Z
1) Please use LaTeX. 2) What is the new contribution to this question? 3) Your reasoning is faulty. Simulating $M$ takes time $\mathcal{O}(n)$ already, to $M*$ can certainly not run in constant time.
Raphael
CC BY-SA 3.0
2011-05-18T23:27:55.567Z
For large enough n, if M(x) halts, then its simulation halts too and returns to M* within n0 (constant) steps.
André Luiz Barbosa
CC BY-SA 3.0
2011-05-18T17:17:27.983Z
2011-07-12T17:22:27.480Z
2011-07-12T17:22:27.480Z
André Luiz Barbosa
<p>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.</p>

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

<p>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)$.</p>

CC BY-SA 2.5
2011-03-15T14:06:39.990Z
@Emanuele: As a heads-up, it appears that your theorem may be a special case of a result that is proved by Jules Hartmanis, on the final page of his monograph <i>Feasible computations and provable complexity properties</i> (1978) ... perhaps I'll post more about this, in a few days, once I have finished digesting Hartmanis' result.
John Sidles
CC BY-SA 3.0
2013-07-16T08:38:59.673Z
This answer inspired the following article: http://arxiv.org/abs/1307.3648
David G
CC BY-SA 3.0
2017-02-15T11:34:02.953Z
@AaronSterling As long as the OP is fine with the edits, there is no problem in rephrasing a section of or even the entire answer. Writing new paras to describe something differently however should be preferably done in comments or a separate answer. (Unless of course, u want to make the answer a community wiki) And I think the automatic change to CW feature has been removed.
ghosts_in_the_code
CC BY-SA 2.5
2011-02-18T17:12:15.683Z
why does M have to halt on x (if it does) in O(1) steps ?
Suresh Venkat
CC BY-SA 2.5
2011-02-18T17:18:13.380Z
$M$ and $x$ are fixed independent of $n$.
Manu
CC BY-SA 2.5
2011-02-18T17:26:25.573Z
Wow, TCS StackOverflow is great!  Emanuele, one thing that baffles me is your answer's lack of reference to the promise that M is in P.  Does the proof of the undecidability of the halting problem still go through, if the halting set is so restricted?  This is not obvious to me (and I would need considerable time to work it through even imperfectly).
John Sidles
CC BY-SA 2.5
2011-02-18T17:46:47.603Z
Upon one further reading (and careful parsing) your answer now has been "accepted"!  Thank you for your trouble, and for a fine answer!
John Sidles
CC BY-SA 2.5
2011-02-18T19:32:25.890Z
John, $M$ is not necessarily in $P$. It is an arbitrarily chosen TM, otherwise you would not reduce the halting problem.
Raphael
CC BY-SA 2.5
2011-02-18T19:41:39.640Z
I think the reduction's central equivalence could have been stated/shown more clearly. Should I just edit and try to improve it?
Raphael
CC BY-SA 2.5
2011-02-18T19:56:20.953Z
Very clever proof, is it a variation of some well-known result or did you just devise it?
Antonio E. Porreca
CC BY-SA 2.5
2011-02-18T20:07:55.453Z
To second Antonio's comment, I would very much like to be able to cite a reference for Emanuele Viola's answer (also Luca Trevisan's answer to a related question, that was linked in the question as-hand).
John Sidles
CC BY-SA 2.5
2011-02-18T21:19:09.463Z
@Raphael: That's a touchy area, which I don't think we've resolved. Some stackexchange sites encourage editing of others' answers. We don't have a policy against it, but, as a practical matter, I've almost never seen it done.  One technical point: if an answer is edited too much, it becomes community wiki, and @Emanuele would not get any further rep points if his answer were upvoted after that.  I do think additional explanation would help clarify: @John Sidles initially thought the promise was not being used, but the proof uses a *stronger* promise: $M'$ runs in $n^2$ or $n^3$, not just P.
Aaron Sterling
CC BY-SA 2.5
2011-02-18T21:52:26.220Z
Ok, then lets do it like this: Emanuele, if you want me to potentially improve the understandibility of your otherwise great answer, please give the word! As I am low-rep, a mod will have to approve my edit, anyway.
Raphael
CC BY-SA 2.5
2011-02-18T21:54:53.957Z
@John: As long as no published reference is given, consider [this guideline](http://meta.cstheory.stackexchange.com/questions/352/how-will-you-cite-a-discussion-on-this-site-in-your-paper).
Raphael
CC BY-SA 2.5
2011-02-18T23:05:08.577Z
@Raphael, I agree with @Aaron Sterling, editing heavily other user's answers has been a very common practice on cstheory. On the other hand you can post another answer trying to explain Emanuele's answer from your view point if you want.
Kaveh
CC BY-SA 2.5
2011-02-18T23:16:23.717Z
Aaron is 100% right ... I had to parse Emanuele's post quite slowly (and enjoyably) in order to grasp its main point.
John Sidles
CC BY-SA 2.5
2011-02-26T21:06:22.900Z
I tried to rewrite this proof in my own words in [this blog entry](http://nanoexplanations.wordpress.com/2011/02/26/determining-the-minimum-polynomial-that-bounds-a-ptime-turing-machine-is-undecidable/).
Aaron Sterling
CC BY-SA 2.5
2011-02-28T14:13:20.550Z
Aaron, your new "Nanoexplanations" weblog is outstanding and I greatly enjoyed your clarified proof. I've posted a comment there that begins: "Scott Aaronson is the author of a wonderful article titled 'Is P Versus NP Formally Independent?' I have often wished that Scott would write a similarly graceful and erudite followup  'Is P Versus NP Formally Undecidable?'  One might say: 'Wait a second … wouldn't these be the same article?' To which the answer is: 'Formally yes … and yet, their guiding intuitions might be very different.'"  Further comments on Aaron's new weblog would be very welcome.
John Sidles
CC BY-SA 2.5
2011-02-18T17:09:55.557Z
2011-02-18T17:09:55.557Z
Manu
<p>The question asked is whether the following question is decidable:</p>
<blockquote>
<p><strong>Problem</strong>  Given an integer <span class="math-container">$k$</span> and Turing machine <span class="math-container">$M$</span> promised to be in P, is the runtime of <span class="math-container">$M$</span> <span class="math-container">${O}(n^k)$</span> with respect to input length <span class="math-container">$n$</span> ?</p>
</blockquote>
<p>A narrow answer of &quot;yes&quot;, &quot;no&quot;, or &quot;open&quot; is acceptable (with references, proof sketch, or a review of present knowledge), but broader answers too are very welcome.</p>
<p><strong>Answer</strong></p>
<p>Emanuele Viola has <a href="https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006">posted a proof</a>  that the question is undecidable (see below).</p>
<p><strong>Background</strong></p>
<p>For me, this question arose naturally in parsing Luca Tevisan's answer to the question <a href="https://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716"><i>Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?</i></a></p>
<p>The question relates also to a MathOverflow question: <a href="https://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics"><i>What are the most attractive Turing undecidable problems in mathematics?</i></a>, in a variation in which the word &quot;mathematics&quot; is changed to &quot;engineering,&quot; in recognition that runtime estimation is an ubiquitous engineering problem associated to (for example) control theory and circuit design.</p>
<p>Thus, the 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 infeasible (that is, require computational resources in EXP to estimate), versus formally undecidable.</p>
<p>--- edit (post-answer) ---</p>
<p>I have added <a href="https://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/55936#55936">Viola's proof</a> to MathOverflow's  community wiki <i>&quot;Attractive Turing-undecidable problems&quot;.</i>  It is that wiki's first contribution associated to the complexity class P; this attests to the novelty, naturality, and broad scope of Viola's proof (and IMHO its beauty too).</p>
<p>--- edit (post-answer) ---</p>
<p>Juris Hartmanis' monograph <i>Feasible computations and provable complexity properties</i> (1978) covers much of the same material as Emanuele Viola's proof.</p>

CC BY-SA 3.0
2011-05-31T23:09:07.860Z
In response to questions posed on Lance Fortnow and Bill GASARCH's weblog, under the topic "75 Years of Computer Science", beginning "I have often wished that Turing had soberly asked: “What are the verifiable processes which can be carried out in computing a number?” ... instead of Turing asking the fatefully harder question: “What are the possible processes which can be carried out in computing a number?”, the next question asked will be (approximately) "Do Turing machines exist that are provably in NP, whose membership in P is undecidable?"   This is to show I'm still thinking about it! :)
John Sidles
CC BY-SA 3.0
2011-06-27T17:34:45.620Z
Although I Emanuele Viola's proof is clearer, a very similar question was asked and answered on Mathoverflow: http://mathoverflow.net/questions/28056/given-a-polynomial-time-algorithm-can-we-compute-an-explicit-polynomial-time-bou
Alex ten Brink
CC BY-SA 3.0
2011-07-07T12:00:22.300Z
Several of the answers and ideas on this thread proved relevant to an essay/question set that Dick Lipton has posted on his weblog *Godel's Lost Letter*; that essay/question set is "Getting On Base With P=NP".  URL: http://rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp/
John Sidles
CC BY-SA 3.0
2011-07-17T19:25:29.887Z
Although the bounds in P are undecidable, it doesn't stop one from trying (by restricting oneself further). An example if given in this [cstheory answer](http://cstheory.stackexchange.com/questions/376/using-lambda-calculus-to-derive-time-complexity/379#379)
Artem Kaznatcheev
CC BY-SA 3.0
2012-09-04T16:32:44.010Z
John, I can't find a similar result/discussion in Hartmanis' book (I only skimmed it, though). Can you please focus the reference a bit more?
Raphael
CC BY-SA 3.0
2013-07-16T08:37:43.637Z
This question inspired the following article: http://arxiv.org/abs/1307.3648
David G
CC BY-SA 3.0
2015-05-03T16:46:56.280Z
In view of @DavidG link the title of the question is misleading. It *is* possible to decide linear running time.
Andrej Bauer
CC BY-SA 3.0
2015-05-08T01:59:53.663Z
What if instead of O(N^k) we wanted to see if M halted in a constant number of steps, 1000 for example. Is this decidable?
TheJKFever
CC BY-SA 3.0
2017-02-15T16:28:58.620Z
Most Rice-theorem-type results like this one are easy to prove if you think in terms of "gas tanks" as I explain in my answer to this related MathOverflow question. http://mathoverflow.net/questions/28056/given-a-polynomial-time-algorithm-can-we-compute-an-explicit-polynomial-time-bo/28060#28060
Timothy Chow
CC BY-SA 4.0
2024-03-20T02:13:06.920Z
There are closely related questions on [cs.se](https://cs.stackexchange.com/q/12518/4678) and (as Timothy Chow notes) [math overflow](https://mathoverflow.net/q/28056/27773).
Neal Young
<cc.complexity-theory><approximation-hardness>
Are runtime bounds in P decidable? (answer: no)
John Sidles
# Are runtime bounds in P decidable? (answer: no)

(Asked by: username_0 on 2011-02-18)

The question asked is whether the following question is decidable:

> **Problem**  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](https://cstheory.stackexchange.com/questions/5004/are-runtime-bounds-in-p-decidable-answer-no/5006#5006) that the question is undecidable (see below).

**Background**

For me, this question arose naturally in parsing Luca Tevisan's answer to the question [*Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?*](https://cstheory.stackexchange.com/questions/4704/do-runtimes-for-p-require-exp-resources-to-upper-bound-are-concrete-examples-k/4716#4716)

The question relates also to a MathOverflow question: [*What are the most attractive Turing undecidable problems in mathematics?*](https://mathoverflow.net/questions/11540/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 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 infeasible (that is, require computational resources in EXP to estimate), versus formally undecidable.

--- edit (post-answer) ---

I have added [Viola's proof](https://mathoverflow.net/questions/11540/what-are-the-most-attractive-turing-undecidable-problems-in-mathematics/55936#55936) to MathOverflow's community wiki *"Attractive Turing-undecidable problems".* It is that wiki's first contribution associated to the complexity class P; this attests to the novelty, naturality, and broad scope of Viola's proof (and IMHO its beauty too).

--- edit (post-answer) ---

Juris Hartmanis' monograph *Feasible computations and provable complexity properties* (1978) covers much of the same material as Emanuele Viola's proof.

**Tags:** cc.complexity-theory, approximation-hardness
> **Comments:**
> **username_0**: In response to questions posed on Lance Fortnow and Bill GASARCH's weblog, under the topic "75 Years of Computer Science", beginning "I have often wished that Turing had soberly asked: “What are the verifiable processes which can be carried out in computing a number?” ... instead of Turing asking the fatefully harder question: “What are the possible processes which can be carried out in computing a number?”, the next question asked will be (approximately) "Do Turing machines exist that are provably in NP, whose membership in P is undecidable?"   This is to show I'm still thinking about it! :)  
> **username_1**: Although I Emanuele Viola's proof is clearer, a very similar question was asked and answered on Mathoverflow: http://mathoverflow.net/questions/28056/given-a-polynomial-time-algorithm-can-we-compute-an-explicit-polynomial-time-bou  
> **username_0**: Several of the answers and ideas on this thread proved relevant to an essay/question set that Dick Lipton has posted on his weblog *Godel's Lost Letter*; that essay/question set is "Getting On Base With P=NP".  URL: http://rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp/  
> **username_2**: Although the bounds in P are undecidable, it doesn't stop one from trying (by restricting oneself further). An example if given in this [cstheory answer](http://cstheory.stackexchange.com/questions/376/using-lambda-calculus-to-derive-time-complexity/379#379)  
> **username_3**: John, I can't find a similar result/discussion in Hartmanis' book (I only skimmed it, though). Can you please focus the reference a bit more?  
> **username_4**: This question inspired the following article: http://arxiv.org/abs/1307.3648  
> **username_5**: In view of @DavidG link the title of the question is misleading. It *is* possible to decide linear running time.  
> **username_6**: What if instead of O(N^k) we wanted to see if M halted in a constant number of steps, 1000 for example. Is this decidable?  
> **username_7**: Most Rice-theorem-type results like this one are easy to prove if you think in terms of "gas tanks" as I explain in my answer to this related MathOverflow question. http://mathoverflow.net/questions/28056/given-a-polynomial-time-algorithm-can-we-compute-an-explicit-polynomial-time-bo/28060#28060  
> **username_8**: There are closely related questions on [cs.se](https://cs.stackexchange.com/q/12518/4678) and (as Timothy Chow notes) [math overflow](https://mathoverflow.net/q/28056/27773).  

---

## 9 answers

### Answer by username_16 on 2011-02-18. Score: 93 | Accepted answer

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'$ 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'$ would be $O(n^2)$. If $M$ never halts then the run time of $M'$ is at least $n^3$.

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

> **Comments:**
> **username_18**: why does M have to halt on x (if it does) in O(1) steps ?  
> **username_16**: $M$ and $x$ are fixed independent of $n$.  
> **username_0**: Wow, TCS StackOverflow is great!  Emanuele, one thing that baffles me is your answer's lack of reference to the promise that M is in P.  Does the proof of the undecidability of the halting problem still go through, if the halting set is so restricted?  This is not obvious to me (and I would need considerable time to work it through even imperfectly).  
> **username_0**: Upon one further reading (and careful parsing) your answer now has been "accepted"!  Thank you for your trouble, and for a fine answer!  
> **username_3**: John, $M$ is not necessarily in $P$. It is an arbitrarily chosen TM, otherwise you would not reduce the halting problem.  
> **username_3**: I think the reduction's central equivalence could have been stated/shown more clearly. Should I just edit and try to improve it?  
> **username_19**: Very clever proof, is it a variation of some well-known result or did you just devise it?  
> **username_0**: To second Antonio's comment, I would very much like to be able to cite a reference for Emanuele Viola's answer (also Luca Trevisan's answer to a related question, that was linked in the question as-hand).  
> **username_20**: @Raphael: That's a touchy area, which I don't think we've resolved. Some stackexchange sites encourage editing of others' answers. We don't have a policy against it, but, as a practical matter, I've almost never seen it done.  One technical point: if an answer is edited too much, it becomes community wiki, and @Emanuele would not get any further rep points if his answer were upvoted after that.  I do think additional explanation would help clarify: @John Sidles initially thought the promise was not being used, but the proof uses a *stronger* promise: $M'$ runs in $n^2$ or $n^3$, not just P.  
> **username_3**: Ok, then lets do it like this: Emanuele, if you want me to potentially improve the understandibility of your otherwise great answer, please give the word! As I am low-rep, a mod will have to approve my edit, anyway.  
> **username_3**: @John: As long as no published reference is given, consider [this guideline](http://meta.cstheory.stackexchange.com/questions/352/how-will-you-cite-a-discussion-on-this-site-in-your-paper).  
> **username_9**: @Raphael, I agree with @Aaron Sterling, editing heavily other user's answers has been a very common practice on cstheory. On the other hand you can post another answer trying to explain Emanuele's answer from your view point if you want.  
> **username_0**: Aaron is 100% right ... I had to parse Emanuele's post quite slowly (and enjoyably) in order to grasp its main point.  
> **username_20**: I tried to rewrite this proof in my own words in [this blog entry](http://nanoexplanations.wordpress.com/2011/02/26/determining-the-minimum-polynomial-that-bounds-a-ptime-turing-machine-is-undecidable/).  
> **username_0**: Aaron, your new "Nanoexplanations" weblog is outstanding and I greatly enjoyed your clarified proof. I've posted a comment there that begins: "Scott Aaronson is the author of a wonderful article titled 'Is P Versus NP Formally Independent?' I have often wished that Scott would write a similarly graceful and erudite followup  'Is P Versus NP Formally Undecidable?'  One might say: 'Wait a second … wouldn't these be the same article?' To which the answer is: 'Formally yes … and yet, their guiding intuitions might be very different.'"  Further comments on Aaron's new weblog would be very welcome.  
> **username_0**: @Emanuele: As a heads-up, it appears that your theorem may be a special case of a result that is proved by Jules Hartmanis, on the final page of his monograph <i>Feasible computations and provable complexity properties</i> (1978) ... perhaps I'll post more about this, in a few days, once I have finished digesting Hartmanis' result.  
> **username_4**: This answer inspired the following article: http://arxiv.org/abs/1307.3648  
> **username_17**: @AaronSterling As long as the OP is fine with the edits, there is no problem in rephrasing a section of or even the entire answer. Writing new paras to describe something differently however should be preferably done in comments or a separate answer. (Unless of course, u want to make the answer a community wiki) And I think the automatic change to CW feature has been removed.  

---

### Answer by username_3 on 2011-02-19. Score: 32

This is a rephrasing of Emanuele Viola's answer with the goal to be more understandable.
We show that the given problem $P$ is undecidable by reducing the general halting problem $H$ to it.
Let $(M, x)$ be any instance of the halting problem, that is we have to decide wether $M(x)\downarrow$ ($M$ halts on $x$). Construct a Turing machine $M^*$ that works as follows:
M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}

Now we observe the following implications:
$\begin{align*} 
  M(x) \downarrow \quad &\Rightarrow \exists n_0 \in \mathbb{N} : M \text{ halts on } x \text{ after at most } n_0 \text{ steps} \\
  &\Rightarrow \forall y : n \geq n_0 \Rightarrow M^*(y) \text{ executes } n^2 \text{ arbitrary steps} \\
  &\Rightarrow T_{M^*}(n) \in \mathcal{O}(n^2)
\end{align*}$
and
$\begin{align*} 
  M(x) \uparrow \quad &\Rightarrow \forall n \in \mathbb{N} : M \text{ does not halt on } x \text{ in less than } n \text{ steps} \\
  &\Rightarrow \forall y :  M^*(y) \text{ executes } n^3 \text{ arbitrary steps} \\
  &\Rightarrow T_{M^*}(n) \in \Omega(n^3)
\end{align*}$
Therefore, $H(M,x) \Leftrightarrow P(M^*,2)$. Assuming $P$ was algorithmicaly decidable, so would be $H$, which yields a contradiction. $\square$


---

### Answer by username_5 on 2015-05-03. Score: 14

On the positive side, it is decidable whether a one-tape Turing machine runs in time $n \mapsto C \cdot n + D$ for given $C, D \in \mathbb{N}$, see:

> David Gajser: *Verifying whether One-Tape Non-Deterministic Turing Machines Run in Time $Cn+D$*, [arXiv:1312.0496](http://arxiv.org/abs/1312.0496)

> **Comments:**
> **username_9**: No shortage of unusual behavior by small-time one-tape TMs. :)  

---

### Answer by username_10 on 2017-02-14. Score: 4

The problem was also solved in my article "[The intensional content of Rice's Theorem](http://dl.acm.org/citation.cfm?id=1328455)" POPL'2008, where I prove that no "complexity clique" is decidable.
A complexity clique is a class of programs closed w.r.t. programs with similar behavior *and* complexity. I also provides necessary conditions for semi-decidable properties.

Programs running in O(n^k) are a complexity clique in the above sense, hence the set is not decidable.

The result has also been recently extended to subrecursive settings (such as P) by Mathieu Hoyrup: [The decidable properties of subrecursive functions](https://hal.inria.fr/hal-01308224/) (ICALP 2016).


---

### Answer by username_11 on 2017-09-14. Score: 2

To add to the previous answers, this problem is not only undecidable but $Σ^0\_2$ complete. Thus, it is undecidable even if the decider has an oracle for the halting problem.

To clarify the completeness, while the P-time promise condition is also $Σ^0\_2$-complete, there is a decidable set of codes $S$ such that all machines in $S$ are polynomial time and the $O(n^2)$ question is $Σ^0\_2$ complete on $S$.

To prove this, choose a $Σ^0\_2$ complete $φ$, $φ(x) ⇔ ∃k ∀m \, ψ(x,k,m)$ with $ψ$ polynomial time computable (for binary numbers).

Then $φ(x)$ holds iff the following machine is $O(n^2)$ where $n$ is the input length (the machine only cares about the input length):

for $k$ in 0 to $n$:  
    if $∀m
        halt  
    wait for $n^2$ steps  
halt

Note that for every not-too-small $c$, whether a program always halts in (for example) $≤n^2+c$ steps is $Π^0\_1$-complete, but asking about bounds in a robust manner gives $Σ^0\_2$-completeness.


---

### Answer by username_12 on 2022-12-29. Score: 0

Not even possible with a halting oracle
Consider function
p=0, r=[halted]
for input:
    if r=[halted]:
        p=p+1
        r=Program Q with input p
    Step r once
wait p

Here "wait" loops for $p \cdot input^h$ times so the for before can be ignored
Here p in bounded and time complexity in $O(input^h)$ iff Q(p) doesn't halt, which is $\sum_2$

Also, this question is in $\sum_2$: Exist a $p$, s.t. for each input $n$, P runs in $p\cdot n^k$ time


---

### Answer by username_13 on 2021-09-02. Score: 0

Here is a proof that to me seems better than the one by Mr Viola in that it does not seemingly abstractly suppose some undecidable sentence.

Theorem. There is no machine R such that R()=1 iff M runs within time O(n^k) given that M is promised to be in P.

Proof.

Fix k to be some value and we obtain the algorithm R(.) which takes as its argument the encoding of a machine only (promised to be in P) and outputs 1 if and only if it runs within time O(n^k). Let the language it decides be denoted R(k)
Construct R\* as follows.
If R outputs 1 on the code R\*, then loop for time n^(k+1),
otherwise, loop for time n^k,
halt.

Now run R on R\*. This machine encoding is in the set R(k) iff it is not in the set R(k) a contradiction.

Hence, neither R\* nor R can exist.

Observe that this is essentially the proof of Rice's Theorem. Observe that we can construct such diagonal arguments for such algorithmically definable properties of Turing machines (modulo some subtleties at the boundaries).


---

### Answer by username_14 on 2015-09-29. Score: -2

here is recent new more systematic analysis/ angles/ results on this question & related ones, introducing the concept of "algorithmic verifiability" and a Rice-like-thm analog for complexity theory. one relevant section from the abstract is follows and there are many other related theorems related to provability of P vs NP etc

* [Why the Concept of Computational Complexity is Hard for Verifiable Mathematics](http://eccc.hpi-web.de/report/2015/159/) / Hromkovic

  > First, we prove Rice's theorem for unprovability, claiming that each nontrivial semantic problem about programs is not almost everywhere solvable in Algorithmically Verifiable "AV"-mathematics. Using this, we show that there are infinitely many algorithms (programs that are provably algorithms) for which there do not exist proofs that they work in polynomial time or that they do not work in polynomial time. ...
  >
  > Note that, if P != NP is provable in AV-mathematics, then for each algorithm A it is provable that "A does not solve SATISFIABILITY or A does not work in polynomial time". Interestingly, we finally show that there exist algorithms for which it is neither provable that they do not work in polynomial time, nor that they do not solve SATISFIABILITY. Moreover, there is an algorithm solving SATISFIABILITY for which one cannot prove in AV-mathematics that it does not work in polynomial time.
  >
  > Furthermore, we show that P = NP implies the existence of algorithms X for which the claim "X solves SATISFIABILITY in polynomial time" is not provable in AV-mathematics.


---

### Answer by username_15 on 2011-05-18. Score: -3

The solution from Viola can be generalized to any running time (beyond poly): You can reduce the halting problem to it as follows. Given an instance (M,x) of the halting problem, construct a new machine M′ that works as follows: on inputs of length n, it simulates M on x for f(n) steps or until M halts, where f(n) is any arbitrary increasing function (greater than constant) of n. (Obs.: M′ reads gradually the input, in order to avoid wasting linear time [O(n)] just to read needlessly all the input, if it is large enough and M halts.)

If M halts on x it does so in T=O(1) steps, so the run time of M′ would be O(1). If M never halts then the run time of M′ is O(n^2\*f(n)).

Hence you can decide if M accepts x by deciding if the run time of M′ is O(1) or O(n^2\*f(n)).

Then, the auxiliary code from Raphael can be generalized accordingly by:

Let (M,x) be any instance of the Halting Problem, that is we have to decide whether M halts on x. Construct a deterministic Turing Machine (DTM) M\* that works as follows:

1. M\*(input) = {
2. n := 0
3. Read the first symbol from the input
4. Loop:
5. n := n+1
6. Simulate M(x) for f(n) steps or until M(x) halts
7. Read the next symbol from the input
8. Loop until end\_of\_input or until M(x) has halted
9. }

Now we observe the following implications:

M halts on x after at most k (constant) steps => T(M\*) = O(1) and

M never halts on x => T(M\*) = O(n^2\*f(n))

Therefore, even deciding whether the running time of an arbitrary DTM is simply greater than constant is as hard as Halting Problem. □

> **Comments:**
> **username_3**: 1) Please use LaTeX. 2) What is the new contribution to this question? 3) Your reasoning is faulty. Simulating $M$ takes time $\mathcal{O}(n)$ already, to $M*$ can certainly not run in constant time.  
> **username_15**: For large enough n, if M(x) halts, then its simulation halts too and returns to M* within n0 (constant) steps.  

---

