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.

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

      Image of Alexander's 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.

share|improve this question
1  
as @Alex ten Brink points out, the Turing machines you talk about in Q1 are not well defined. I think you need to think about the $\forall$'s and $\exists$'s in your question as opposed to Viola's proof. –  Sasho Nikolov Jun 21 '11 at 2:47
    
@Shasho, thank you ... an acknowledgement and summary of Alex's points (and Travis Service's points too) has been added to the question asked. –  John Sidles Jun 21 '11 at 8:42
1  
Note that Emanuele Viola's proof applies to a very broad range of problems: a generalised version proves for any time-constructible functions $f, g$ with $f(n) = \omega(n \log n)$ and $g(n) = \omega(f(n))$ that it is impossible for a TM for which it is promised it halts in $t(n)$ time and also that $t(n)=O(f(n))$, to decide whether $t(n) = \omega(f(n))$ and $t(n)=O(g(n))$. I don't really see the link to $P$ vs $NP$ here. –  Alex ten Brink Jun 21 '11 at 12:40
2  
For me, the link to P vs NP arises by analogy to geometry. Definitions that formalize the notion of a continuum are broadly stratified from Kahler manifolds to Riemann manifolds to smooth manifolds to topological manifolds to point sets (with many further distinctions), and formalizing these distinctions was essential to progress in mathematics. Similarly, the set of Turing machines in P, and the set of languages these machines accept, seemingly includes "wild" algorithms whose role in complexity theory is (perhaps?) broadly analogous to "exotic" point sets in geometry and topology. –  John Sidles Jun 21 '11 at 14:16
1  
@John, I've seen hints of these thoughts in your (various earlier.. maybe much earlier) blog comments, and I'm quite pleased to see how far you've progressed down the line with it. Cool! –  Daniel Apon Jun 29 '11 at 16:37
show 4 more comments

4 Answers 4

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.

share|improve this answer
5  
Travis does answer the rephrased question, but this is a strange situation where there is a provable exponent but only for machines you cannot prove solves the problem. –  Lance Fortnow Jun 20 '11 at 22:10
    
This is a nice answer to Q1 ... and I completely agree with Lance that this algorithm is a very strange member of class P. Part of the motivation of the question was to capture the intuition (via definitions that are nice for theorem-proving) that the algorithms in P that we "care about" (in some sense) are the algorithms whose performance we can "verify" (in some sense) ... this example utterly defeats that purpose! Nice answer! :) –  John Sidles Jun 21 '11 at 1:45
    
This fine comment (which I am still thinking about) called to mind Felix Klein's remark "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." The point is that to make progress on P versus NP, perhaps a key step is to refine the definition of P to exclude "countless possible abnormalities." –  John Sidles Jun 21 '11 at 7:18
2  
Your answer is very interesting. However, predicate 1 might be more accurately described as 'There does not exist a proof that $N$ accepts $L$ starting from the definition below.', since I can easily construct a TM deciding $L$ (which is the empty language), and prove it always halts and decides the empty language. I learned something nice again, and I'm going to check up on that reference you mentioned :D –  Alex ten Brink Jun 22 '11 at 21:09
    
Travis' edit of his already-good answer provides even more to think about. Since this process will take awhile (for me), I would like to express my appreciation and thanks now (and technical remarks later) to both both Travis (Service) and Alex (ten Brink). Though they are students, their comments (IMHO) have been mature and interesting. It's well-known that Alan Turing conceived his "On Computable Numbers, with an Application to the Entscheidungsproblem" between his 21st and 23rd years; thus students have attacked similar problems with success ... we may hope the same for Alex & Travis. –  John Sidles Jun 23 '11 at 13:27
add comment

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.

share|improve this answer
    
Yes ... that trick is the essence of Emanuele Viola's and Juris Harmanis' proofs of P's runtime undecidability (for example). On the other hand, it is trivially the case that the Turing machines that are constructed by this trick all recognize languages L that are also recognized by Turing machines in P whose runtimes are decidable. This is why Q1 is phrased (carefully!) as a question about languages rather than about Turing machines ... precisely in order to exclude the Hartmanis/Viola construction ... without obstructing (per your comment) the existing proofs that P \ne EXP. –  John Sidles Jun 20 '11 at 20:15
    
... and just to mention, those language L that are recognized solely by Turing machines whose runtime exponents were undecidable, are interesting languages from a complexity-theoretic (and cryptographic) point-of-view ... they seemingly exist in a Godel-esque "gray region" between algorithmically compressible (but by definition not verifiably so) and incompressible (and yet by definition not in that class either). –  John Sidles Jun 20 '11 at 20:39
add comment

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.

share|improve this answer
    
This is a very powerful and flexible argument, and it will take awhile for me to grasp it ... there's a saying among farmers in the central USA "I feel like a pig being shown a wristwatch!" It appears (by your argument) that P is richly endowed with undecidable attributes; what I am having trouble grasping is whether the languages L recognized by P similarly are richly endowed with undecidable attributes ... the exercise of constructing concrete example languages having natural undecidable attributes is particularly frustrating (for me). Thank you for an excellent, thought-provoking answer. –  John Sidles Jun 22 '11 at 10:35
1  
I think you believe $P$ to be the set of TMs running in polynomial time. This is not the definition: $P$ is the set of languages decidable by some TM running in polynomial time. –  Alex ten Brink Jun 22 '11 at 12:17
    
Alex, I definitely confess to being confused ... but not about that! What I would like to construct, or (less desirably) prove the existence/nonexistence of, would be (for example) a language L in P having the property that every Turing machine that accepts L either is not verifiably in P or does not verifiably accept L. These languages L would belong to P "oracularly" ... the possibility that P includes purely oracular languages is confusing to me ... especially since it is at all not obvious (to me) how such purely oracular languages could ever be concretely sampled and exhibited. –  John Sidles Jun 22 '11 at 15:34
    
Oh yeah ... and to ask the converse (also confusing) question ... for a given language L in NP that possibly is accepted solely by oracular Turing machines ... by what proof method could we possibly establish that L is not recognized by any of P's oracular Turing machines ... and thus separate P from NP? Or suppose that we did prove the existence of a language L in NP not recognized by any Turing machine in P ... with the restriction that L was purely oracular ... and we could not exhibit that language ... should we be satisfied that P != NP? These questions are confusing! –  John Sidles Jun 22 '11 at 17:09
add comment

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.

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.

share|improve this answer
    
your comment and Travis Service' account both are excellent. It appears that in Q1 the phrase "undecidable" is not synonymous with "not verifiably decidable" ... and it is not at all clear (to me) which definition (a) leads to the best theorems and (b) best captures our intuition of the class P. Remarks on this question are welcome. –  John Sidles Jun 21 '11 at 7:34
    
Thank you Alex for the link (to the MOF question "Can a problem be simultaneously polynomial time and undecidable?") ... I have edited the main post to include that link. –  John Sidles Jun 28 '11 at 13:04
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.