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

I have added Viola's proof 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).

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! :) May 31, 2011 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/… Jun 27, 2011 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 Jul 7, 2011 at 12:00
• This question inspired the following article: arxiv.org/abs/1307.3648 Jul 16, 2013 at 8:37
• 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. mathoverflow.net/questions/28056/… Feb 15, 2017 at 16:28

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 ? Feb 18, 2011 at 17:12
• $M$ and $x$ are fixed independent of $n$.
– Manu
Feb 18, 2011 at 17:18
• Very clever proof, is it a variation of some well-known result or did you just devise it? Feb 18, 2011 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. Feb 18, 2011 at 21:19
• @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. Mar 15, 2011 at 14:06

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. :) May 3, 2015 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 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(<M,k>)=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).

# 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

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