Determining the minimum polynomial that bounds a PTIME Turing Machine is undecidable

Posted on February 26, 2011 | 8 Comments

This blog post is motivated by a question John Sidles recently asked on the Theoretical Computer Science Q&A site. Emanuele Viola answered it (providing a very clever proof), and Raphael (I don’t know his last name) rephrased that answer, hoping the proof would be a bit clearer. I think things might be made clearer still, so this is my attempt to express Emanuele’s fine idea in my own words.

Suppose we know for sure that a Turing machine runs in polynomial time. The question is: can we say more than that? Is there some algorithm to determine the minimum $k$ so that the Turing machine runs in $\mathcal{O}(n^k)$ ? Unfortunately, the answer is NO.

Proposition: Let $M \in \mathsf{PTIME}$ be a Turing machine. There is no algorithm that determines the minimum $k$ such that $M \in \mathcal{O}(n^k)$ .

Proof: We will show that if we can solve this problem, we can solve the Halting Problem. Let $N$ be an arbitrary Turing machine, and $x$ an arbitrary natural number (intuitively, $x$ is an input to $N$ ). Now define the Turing machine $M$ as follows:

Let $n$ be the length (i.e., number of bits) of the input to $M$ .
Simulate $N$ running with input $x$ for $n$ steps.
If $N$ accepts during step 2, loop for $n^2$ steps and then halt.
Otherwise, loop for $n^3$ steps and then halt.

Note that the value of $x$ is independent of the choice of input to $M$ . So $M \in \mathcal{O}(n^2)$ iff $N$ halts on $x$ , and $M \in \mathcal{O}(n^3)$ iff $N$ does not halt on $x$ . We know that $M$ is in $\mathsf{PTIME}$ . (In fact, we know something stronger: it is either in $\mathcal{O}(n^2)$ or $\mathcal{O}(n^3)$ .) If we could determine the minimum exponent $k$ (for simplicity, either 2 or 3) such that $n^k$ upper-bounds the running time of $M$ , we would be able to decide whether an arbitrary Turing machine accepts an arbitrary input — the Halting Problem. So no algorithm can exist that will provide us the value of $k$ . $\Box$

I really like this argument. It’s almost poetic: nothing unnecessary included.

About these ads

This entry was posted in Uncategorized and tagged computational complexity, Halting Problem, polynomial time. Bookmark the permalink.

8 Responses to Determining the minimum polynomial that bounds a PTIME Turing Machine is undecidable

John Sidles | February 26, 2011 at 3:00 pm | Reply

I am still trying to understand what Viola’s theorem “means” … that is to say, to decide what mathematical narrative(s) Viola’s theorem suggests.

My old intuition was that the set of Turing machines {M} associated to the complexity class P possessed a natural ordering associated to runtime exponents … now that Viola’s theorem tells us that {M} has no decidable ordering, does it follow that the set of languages L in P has no decidable runtime-exponent ordering either?

We appreciate that even today, 45 years after the complexity class P was first formally defined, it is still a mysterious class; this is a theme that Ketan Mulmuley’s lectures (for example) have been emphasizing for some time.
John Sidles | February 28, 2011 at 8:00 am | Reply

Scott Aaronson is the author of a wonderfully interesting article titled Is P Versus NP Formally Independent?, and I have often wished that Scott would write a similarly graceful and erudite companion article with the title 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.” Sufficiently different that (as envisioned) the second article would never use the word “independent”, just as Scott’s first article never uses the word “undecidable”.

MathOverflow hosts a community wiki titled “What are the most attractive Turing undecidable problems in mathematics?” As background, this community wiki is a year old; it has attracted five thousand views; and new candidates are suggested roughly once per week—it is one of the most-active and highest-reputed of all MathOverflow community wikis.

So far, this MathOverflow wiki lists (AFAICT) precisely one undecidable problem that is associated to P versus NP, but it is a natural one: it is Emanuele Viola’s Theorem, which asserts that “Runtime bounds in P are undecidable.”

Although I am very far from being a complexity theory expert, from Emanuele Viola’s Theorem it seems that we can construct a large class of undecidable questions in complexity theory that possess an attractive naturality. Four examples might be: (1) “Given a Turing machine M whose runtime is promised to be exponential, is the language that M recognizes in P?” (2) “Given a Turing machine M whose runtime is promised to be exponential, is the language that M recognizes in NP?” (3) “Given an ordering of the set of polynomial-time algorithms {M}, is that ordering monotonic in runtime exponent?” (3) “Given an ordering of languages in P, is that ordering monotonic in least Turing runtime exponent?”

These four undecidable(?) questions are rough-draft candidates for a formal TCS StackExchange question that I am hopeful of posting later this week).

Aside from their practical engineering implcations, what might these (and other) undecidability theorems imply for the P versus NP question?

Well, we can imagine that we live in an Impagliazzo-style “world” in which the class NP\P is non-empty, but is composed solely of these mysterious undecidable-runtime algorithms … and in this world (AFAICT) the P versus NP question plausibly would be formally undecidable. Indeed, this possibility is one motivation for even posing the question “Are runtime bounds in P decidable?”

That is why it might be interesting to systematically extend the list of provably undecidable questions associated to the classes P and NP; a list that plausibly might grow to be lengthy, natural, and mathematically rigorous … such a list might be a suitable candidate as a community wiki on TCS StackExchange and/or MathOverflow (hmmm … but which forum would be better?). The overall motivation is that deciding the P versus NP question will require a thorough appreciation of the (many) attributes of complexity classes that are formally undecidable … and so we might as well systematically survey these attributes.

There is a quote by Felix Klein regarding the notion of “curve” that speaks also to our present understanding of the complexity cl;asses P and NP:

Another example of a concept which occurs with more or less precision in the naive perception of space, which we must add as a supplement to our system of geometry, is the notion of an (arbitrary) curve. Every person believes that he knows what a curve is until he has learned so much mathematics that the countless possible abnormalities confuse them. … We shall state simply that for us a curve is the totality of points whose coordinates are condinuous functions [that] are differentiable as many times as may be necessary.

Hmmm … Klein’s reasoning guides us to the intuition that restricting P and NP to subclasses that have a decidable runtime ordering is very natural from an engineering point of view … it is broadly analogous to restricting our attention to continuous curves and smooth manifolds. And if a similar runtime-ordering restriction helps us to prove separations among complexity classes, all the better (from a practical engineering point-of-view).

In this regard, suggestions of all kinds from readers of Nanoexplanations would be very welcome, and especially, further suggestions for natural attributes of complexity classes that are formally undecidable, would be most welcome of all!
Doug Mounce | February 28, 2011 at 12:25 pm | Reply

Poincare’ said something similar to Felix Klein, albeit in defense of
the speculative analysis more popular among the geometers in Paris compared to the Germans at Gottingen.

“The sole natural object of mathematical thought is the whole number. It is the external world that has imposed the continuous upon us…

“…we have devoted almost all our time and all our strength to the study of the continuous. Who will regret it; who will think that this time and this strength have been wasted? Analysis unfolds before us infinite perspectives that arithmetic never suspects; it shows us at a glance a majestic assemblage whose array is simple and symmetric; on the contrary, in the theory of numbers, where reigns the unforseen, the view is, so to speak, blocked at every step.”

Poincare’ at the first Int’l Congress of Mathematics, Zurich, 1897.
chazisop | March 1, 2011 at 1:53 am | Reply

This is not a surprice. Since the property is non-trivial, by the Rice Theorem we would expect to not be decidable by a Turing Machine. It is good to have a more in depth proof, however. Also, I want to add that the given TM is the input that is used for the “diagonalization” argument and not the TM that decides the given problem. This confused me a bit at start.
John Sidles | March 1, 2011 at 7:36 am | Reply

For me, the extra value associated to Viola’s theorem, relative to Rice’s theorem, is that Viola’s theorem associates undecidability to a restricted class of Turing machines (namely, Turing machines that compute total functions in PTIME), whereas Rice’s theorem applies to a very much broader class of Turing machines (namely, Turing machines that compute partial functions possibly requiring EXPTIME or more).

Upon first exposure to complexity theory, engineers in particular might hope to evade the various paradoxes and pathologies that are associated to undecidability by restricting our attention to algorithms in P. What Viola’s theorem shows us is that this hope fails; the broad algorithmic undecidability associated to Rice’s theorem “leaks” even into the restricted class P.

Section 1.5.2 of Sanjeev Arora and Boaz Barak’s Computational Complexity: a Modern Approach is titled “Criticisms of P and some efforts to address them” … I wish this section were longer, and included a discussion of Viola’s theorem.

Thus for engineers especially, a key criticism of P as a complexity class is that it is defined too broadly … so broadly that at present complexity theory tells us very little about P (not even whether it is separable from NP).

This is why engineers self-impose (in effect) a restriction of P to algorithms whose runtime exponents are decidable. Does this restriction exclude any algorithms of substantial practical utility? That is a very interesting question.
Raphael | July 9, 2011 at 12:27 pm | Reply

chazisop, I think Rice’s theorem is not directly applicable here. We only demand a decision procedure on the set of polynomial time machines, not arbitrary ones. Rice’s theorem only holds if you demand a decision for _any_ input TM.
Elandalussi | August 9, 2011 at 9:11 am | Reply

You wrote:
“So $M \in \mathcal{O}(n^2)$ iff N halts on x, and $M \in \mathcal{O}(n^3)$ iff N does not halt on x.”

How do you infere that N never halts ?
The huge distinction between your proof & Viola’s one is the word: “never”
Viola states clearly the hypothesis that N never halts, in his own words: “If M never halts then the run time of M’ is at least n^3.” So he can derive easily the conclusion. The result of the halting problem instance in his proof is taken as a criteria: if it halts then … if it NEVER halts then …
Am i correct ? (Comment edited to render LaTex -AS)
- Aaron Sterling | August 9, 2011 at 10:22 am | Reply
  
  Thanks for the comment, Elandalussi. It points out an inaccuracy of mine. In the sentence you quoted, I should have used big-Theta, instead of big-O. So $M \in \Theta(n^2)$ iff $N$ halts on $x$ , and $M \in \Theta(n^3)$ iff $N$ does not halt on $x$ , is what I should have said, because we want to be able to decide whether $N$ halts on $x$ , just by knowing whether the exponent of $n$ is 2 or 3. (This is what I “meant,” but I was sloppy when I wrote it up.)
  We don’t need the fact that $N$ never halts, as long as we can decide the set $\{ \langle e,x \rangle \mid$ Turing program $e$ halts on input $x \}$ . That problem is in the same Turing degree as the set of Turing programs that halt, i.e., is complete for computably enumerable sets.