Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
1  
This question inspired the following article: arxiv.org/abs/1307.3648 –  David G Jul 16 '13 at 8:37
show 1 more comment

3 Answers 3

up vote 62 down vote accepted

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

share|improve this answer
4  
why does M have to halt on x (if it does) in O(1) steps ? –  Suresh Venkat Feb 18 '11 at 17:12
5  
$M$ and $x$ are fixed independent of $n$. –  Emanuele Viola Feb 18 '11 at 17:18
2  
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
2  
@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
2  
I tried to rewrite this proof in my own words in this blog entry. –  Aaron Sterling Feb 26 '11 at 21:06
show 12 more comments

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$

share|improve this answer
2  
I think the $\mathcal{O}(n^3)$ should be a $\Omega(n^3)$. Anyway, unless I'm missing something, the proof can be also adapted to the $n$ vs $n^2$ case. –  Antonio Valerio Miceli-Barone May 4 '11 at 21:39
add comment

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

share|improve this answer
2  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.