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

Question

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

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

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

Answer 1

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

Answer 2

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 3

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

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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 8

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 / 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 9

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