# Are runtime bounds in P decidable? (answer: no)

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.

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 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 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 theorem 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 theorem (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.

• 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 May 31 '11 at 23:09
• Although I Emanuele Viola's proof is clearer, a very similar question was asked and answered on Mathoverflow: mathoverflow.net/questions/28056/… – Alex ten Brink Jun 27 '11 at 17:34
• 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: rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp – John Sidles Jul 7 '11 at 12:00
• 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 – Artem Kaznatcheev Jul 17 '11 at 19:25
• This question inspired the following article: arxiv.org/abs/1307.3648 – David G Jul 16 '13 at 8:37

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

• why does M have to halt on x (if it does) in O(1) steps ? – Suresh Venkat Feb 18 '11 at 17:12
• $M$ and $x$ are fixed independent of $n$. – Manu Feb 18 '11 at 17:18
• Very clever proof, is it a variation of some well-known result or did you just devise it? – Antonio E. Porreca Feb 18 '11 at 19:56
• @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 Feb 18 '11 at 21:19
• @John: As long as no published reference is given, consider this guideline. – Raphael Feb 18 '11 at 21:54

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$

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

• No shortage of unusual behavior by small-time one-tape TMs. :) – Kaveh May 3 '15 at 21:56

The problem was also solved in my article "The intensional content of Rice's Theorem" 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 (ICALP 2016).

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<n \, ψ(x,k,m)$: # tested using a loop
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.

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

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

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

• 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 May 18 '11 at 20:49
• For large enough n, if M(x) halts, then its simulation halts too and returns to M* within n0 (constant) steps. – André Luiz Barbosa May 18 '11 at 23:27