Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)

Question

Five linked questions are asked, and a single integrated answer is hoped-for:

• Q1: Do there exist languages $L$ that are recognized solely by those Turing machines in $P$ whose runtime exponents are undecidable?
• Q2: Can examples of these Turing machines be finitely constructed?
• Q3: Can these Turing machines be concretely instantiated? (e.g., by oracles that "guess" them rather than finitely construct them).
• Q4: What other attributes of P (besides runtime exponents) are presently known to be undecidable? For what attributes of $P$ is this question open?
• Q5: Do the undecidable attributes of $P$ pose an obstruction to the decidability of $P \ne NP$?

Note carefully the word "solely" in Q1 (which excludes Lance Fortnow's suggested answer).

---

Conclusions and Conversion to Community Wiki

• The question asked, "Do the undecidable attributes of P pose an obstruction to deciding P versus NP?", is open and believed to be difficult, as are numerous specific questions (like Q1–4 above) that are naturally associated to it.

• Juris Hartmanis' 1978 monograph Feasible Computations and Provable Complexity Properties provides a good entré into the literature and (apparently) there has been no review published since Hartmanis'.

• This class of questions is sufficiently unexplored that the challenge of finding rigorous proofs is intimately admixed with the challenge of choosing good starting definitions.

• The thoughtful remarks and insightful proof sketches provided by Travis Service and Alex ten Brink are acknowledged and appreciated.

Because the question is open, and because it is being discussed on multiple mathematical weblog threads (1,2,3,4,5,6), this question has been flagged for conversion to Community Wiki.

---

Update II and Summary

I have become aware that Juris Harmanis’ 1978 monograph Feasible Computations and Provable Complexity Properties can be read as an in-depth response to Q1–5. Moreover, the (excellent) Q1 and Q4 proof sketches provided below by Travis Service and by Alex ten Brink provide a modern affirmation and extension of Hartmanis' overall conclusions that:

Results about the complexity of computations change quite radically if we consider only properties of computations which can be proven formally (emphasis by Hartmanis) ...

Thus we should expect that the results about the optimality of all programs computing the same function as a given program will differ from the optimality results about all programs which can be formally proven to be equivalent to the given program. ...

We [should] consider the possibility that this famous problem [$P\overset{?}{=}NP$] may not be solvable in a formalized mathematical theory, such as set theory.

Eventually I hope to post, as a formal TCS StackExchange "answer", further quotations from Hartmanis' (remarkably foresighted) monograph.

It's evident from both Hartmanis' monograph and from the answers provided by Travis and Alex, that Q1–5 are considerably beyond the present state-of-the-art in complexity theory. Moreover these questions/answers evidently are sufficiently subtle as to require careful definitional adjustments and justify monograph-length expositions … which I hope will not discourage people from posting further answers. :)

For further technical discussion, see Joel David Hamkins' answer on MathOverflow to the question Can a problem be simultaneously polynomial time and undecidable? (recommended by Alex ten Brink).

If in Hartmanis’ monograph one substitutes for “computation of functions” the phrase “simulation of dynamics”, the result can be read as a treatise on the complexity-theoretic limits to systems engineering … this is the practical reason why we engineers care about these issues.

A contrasting opinion to Hartmanis' was recently voiced by Oded Goldreich in a letter to the CACM editor titled "On Computational Complexity":

Unfortunately, we currently lack good theoretical answers to most natural questions regarding efficient computation. This is the case not because we ask the wrong questions, but rather because these questions are very hard.

It is (of course) perfectly conceivable that both Hartmanis' and Goldreich's opinions will prove to be correct, for example, a formal proof of the undecidability of the separability of PvsNP could reasonably be regarded as validating both points-of-view.

---

Update I

Thoughtful comments (below) by Travis Service and Alex ten Brink suggest (in effect) that in Q1 the phrase "undecidable" is not synonymous with "not verifiably decidable" and that the answers to Q2–5 may depend upon this distinction. It is not at all clear (to me) which definitional choice would lead to the strongest theorems, and also, best capture our intuition of the class P. Answers and comments that address this question are welcome.

A remark by Felix Klein in his Elementary Mathematics from an Advanced Standpoint: Geometry (1939) comes to mind:

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.

As with curves, so with the languages accepted by Turing machines in $P$ … what once seemed (to me) like the simplest and most natural of all complexity classes now confuses me by the (countless?) unverifiable and/or undecidable attributes of its members. The broad motivation in asking Q1–5 was to find a path through this confusing thicket, but the answers given so far (by Travis Service and Alex ten Brink) have provided further grounds for confusion!

Klein's generation of mathematicians labored mightily to find good definitions for curves and other fundamental elements of set theory, geometry and analysis. An elementary-level overview can be found in the Wikipedia discussion of the Alexander Horned Sphere

      
      An embedding of a sphere in R3

During the 20th century, analysis of "wild manifolds" like the Alexander sphere helped clarify the distinctions between topological manifolds, piecewise-continuous manifolds, and differential manifolds. Similarly in the 21st century, perhaps refinements of the definitions associated to $P$ will help tame $P$'s wild languages and wild Turing machines … although specifying suitable refinements will be no easy task.

---

Background

These linked questions arise from the MathOverflow community wiki questions "What are the most attractive Turing undecidable problems in mathematics?" and "What notions are used but not clearly defined in modern mathematics?" In particular, Colin Tan requested that the question asked above be posted as a separate question.

For technical background see the TCS StackExchange question "Are runtime bounds in P decidable?", in particular Emanuele Viola's concise proof that the answer is "no". Note also that similar results are proved by Juris Hartmanis in his monograph Feasible computations and provable complexity properties (1978).

This week's Lance Fortnow/Bill GASARCH weblog Computational Complexity is hosting their decadal poll "Does $P=NP$ or Not?" -- the fifth and final question asked invites commentary upon the Fortnow/GASARCH question.

Answer 1

For question 1 the answer is no. Let $L$ a language in $P$ and let $M$ be any polynomial time Turing machine recognizing $L$ (whose runtime is assumed to be undecidable). For each $k \in \mathbb{N}$ let $M_k$ be the Turing machine that on input $x$ of length $n$ first loops for $n^k$ steps then runs $M$ on $x$ for $n^k + k$ steps and accepts if $M$ accepts $x$ (within those $n^k + k$ steps) and rejects otherwise. The runtime of $M_k$ is $\Theta(n^k)$ for each $k$.

Since $M$ runs in polynomial time there is some $k' \in \mathbb{N}$ such that $M$ runs in $O(n^{k'})$ (even if we don't know what $k'$ is) and hence for all $k$ large enough $M_k$ recognizes $L$ and has a decidable runtime.

EDIT

I think the following answer is more in spirit of what the original poster had intended with question 1.

Theorem: There exists a language $L \in P$ such that if $N$ is any Turing Machine which decides $L$ then at least one of the following is true:

1) There does not exist a proof that $N$ accepts $L$, or

2) There does not exist a proof that $N$ halts in $f(n)$ steps (for any function $f(n)$).

Proof Sketch: Let $M$ be a Turing Machine that does not halt on the blank tape and for which there does not exist a proof that $M$ does not halt on the blank tape (Independence results in Computer Science by Hartmanis and Hopcroft shows such an $M$ can be effectively found).

Let $L = \{ n : \exists n' \geq n \mbox{ s.t. } M \mbox{ halts in } n' \mbox{ steps when run blank tape}\}$.

Since $M$ does not halt, $L$ is in fact the empty language but there is no proof of that (as that would prove that $M$ does not halt).

Let $N$ be any Turing Machine. If there exists both a proof that $N$ decides $L$ and a proof that $N$ runs in $f(n)$ steps then the execution of $N$ when run on input $1$ provides either a proof that $M$ halts (i.e., if $N$ accepts) or that $M$ does not halt (i.e., if $N$ rejects). Thus, if $N$ provably decides $L$ then $N$'s runtime is not decidable and vice versa.

Answer 2

Yes you can build a machine that takes time DTIME($n^{i+1}$)-DTIME($n^i$) where $i$ is the number of steps taken by a specific Turing machine to halt on blank tape. Easy to construct and similar constructions hold for just about any non-trivial aspect of P. Tells us little about whether P v NP is undecidable: No problem proving P $\neq$ EXP despite the same issues.

Answer 3

After thinking more on the subject, I think I found a (possible) answer for your Q4.

• Q4: What other attributes of $P$ (besides runtime exponents) are presently known to be undecidable? For what attributes of $P$ is this question open?

I proved a variation on Rice's theorem that answers your question for most properties. I'll try to explain myself clearer this time (Travis Service's answer was much clearer and more general than my previous answer).

Theorem: For any property holding on some nonempty set of decidable infinite languages (but on no finite languages), it is undecidable whether a given Turing Machine $E$ decides a language with that property, when promised that $E$ always halts in $O(f(n))$ time, where $f(n)=\Omega(n \log n)$ and $f(n)=\Omega(g(n))$, where $g(n)$ is the running time for some Turing Machine deciding some language with that property.

Recall that a Turing Machine (TM from now on) decides a language if it accepts all strings in the language and rejects all strings outside the language. Note that we can take $f(n)$ to be something other than a polynomial, so the theorem is more general than just $P$.

We formalise the notion of a 'property' as some freely selectable set of languages $S$ 'with that property'. Deciding whether a language has the property is then equivalent to deciding whether the language is a member of $S$. Just like in Rice's theorem, we investigate if we can decide whether the language decided by the input TM has the specified property, and so is in $S$. Note that we require $S \subseteq R$, ie, that $S$ contains only decidable languages.

Please note that we are talking about properties of languages, not of TMs. Your question about runtime exponents is not a special case of this theorem. Properties of, say, $P$, studyable by taking $S \subseteq P$, may interest you more than properties of TMs running in polynomial time. You can do all sorts of cruel stuff to a TM, while retaining its correctness and running time, but you can't do the same to languages.

The requirement that all languages in $S$ have to be infinite is a technicality needed for the proof, but since all finite languages are decidable in constant time and are therefore usually uninteresting, I don't think it's a major one. I expect the generalised version that also allows finite languages to be true as well.

Proof of the theorem. Assume we are given some TM $P(E)$ with a TM $E$ as parameter, such that $P$ always halts and accepts iff $E$ decides some language in $S$, and where $E$ is promised to always halt with running times as above. Let $(A, i)$ be an instance for the Halting Problem, ie, $A$ is a TM and $i$ is an input for $A$, and we now want to decide whether $A$ halts on $i$.

Since we assumed $S$ was nonempty, we have some $s \in S$. Since $S$ contains only decidable languages, there exists some TM $C$ deciding $s$. In particular, we choose the $C$ with running time $g(n)$ as assumed in the theorem. We now consider the following TM:

function H(x)
h := simulate A on i for |X| steps and return whether it halted
if h == 'halted' then
    reject
else
    if C(x) accepts then
        accept
    else
        reject
    fi
fi

It is easily seen that the running time of this TM meets the requirements for the theorem, since TMs can be simulated in $O(n \log n)$ time.

We claim that $P(H)$ returns no iff $A$ halts on $i$. Assume $A$ halts on $i$ after $t$ steps. $H$ therefore rejects any $X$ with $|X| \geq t$. We therefore decide at most a finite language, and hence $H$ decides no language in $S$ and $P(H)$ will therefore return no.

Now assume $A$ does not halt on $i$. Then the variable halt will never get the value 'halted', so we decide the same language as $C$, which is exactly $s \in S$, so $P(H)$ will return true. This proves that $P(H)$ can solve the Halting Problem, which in turn proves the theorem.

Answer 4

I can answer your Q1 in the negative, thereby also answering Q2 and Q3 in the negative. I'm not sure about Q4 or Q5 though.

• Q1: Do there exist languages $L$ that are recognized solely by those Turing machines in $P$ whose runtime exponents are undecidable?

It seems you misunderstood exactly what Emanuele Viola proved in his brilliant proof you linked. He showed that there is no single Turing Machine $M$ capable of computing the runtime exponent for any Turing Machine $T$ presented to $M$, even under the promise that $T$ runs in polynomial time.

However, for any given Turing Machine $T$ running in polynomial time, there exists some $k$ such that $T$ has a running time of $O(n^k)$, and hence the Turing Machine $M$ returning $k$ (and nothing more) is able to 'tell' the running time exponent of $T$, even without having to look at $T$! Hence, M decides (in constant time even) what $k$ is for this given Turing Machine $T$. We may not know which Turing Machine decides it, but we know one exists.

Coming back to your question, if we are given a language $L$ in $P$, then there is some Turing Machine $T$ running in $O(n^k)$ for some $k$ that decides $L$, and hence there is the Turing Machine $M$ returning $k$ that decides the runtime exponent for $T$. This answers your question in the negative.

You might instead wonder about a different problem for a given language $L$ in $P$: given Turing Machine $T$ promised to run in polynomial time and promised to decide $L$, is it decidable to find the runtime exponent of $T$?

Unfortunately, this is also undecidable. Suppose we are given a language $L$ in $P$ and a TM (Turing Machine) $M$ capable of deciding for a given TM $T$ promised to run in polynomial time and promised to decide $L$, what the runtime exponent of $T$ is. We can prove this to be undecidable in a very similar way to what Emanuele Viola did: we use the exact TM he defined, and change it slightly: we now want this TM to decide $L$.

Since $L$ is in $P$, there is some TM deciding $L$ in $O(n^k)$ time. Our new TM $M$ first starts exactly as in Emanuele Viola's proof, running the (Halting Problem) TM for $n$ steps. It then loops either for $n^{k+1}$ steps or $n^{k+2}$ steps similarly to Emanuele Viola's TM. Finally, it solves $L$ on the given input and returns the answer.

$M$ is in $P$, decides $L$, and if we know the runtime exponent, we can decide the Halting Problem, so the above problem is also undecidable (for any language $L$). Note that we do not need to know $k$, we don't actually have to construct $M$, all we have to do is know it exists!

This kind of thinking about undecidability is quite common apparently, I remember a (blog?) post about a very similar issue: the question was "is it decidable whether Pi has a 'last zero'", so whether Pi stops having zeroes in its decimal representation if you go down far enough that representation. We currently don't know whether this is the case. We might not even be able to prove it, ever, or it might even be independent from our axiom systems (and thereby unprovable). But, since the answer is either true or false, a TM returning true and a TM returning false decide the issue either case and therefore the problem is decidable.

I'll see if I can find that post on the internet somewhere.

Edit:

I found it on Mathoverflow.