0
$\begingroup$
  1. It seems correct that any single given algorithm must either have polynomial runtime or not. Is there a specific algorithm that (does or does not actually lie in $P$, but) can neither be proven nor disproven to do so?

  2. Is there a decision procedure for "$\in P$"?

  3. Do we know $P$ vs. $NP$ to be decidable? Could it be proven undecidable in the way that an algorithm with proven "optimal" (i. e. proven asymptotically fastest) runtime is non-constructively provided, and then one proves that it is undecidable whether the optimal algorithm has polynomial runtime or not?

$\endgroup$
  • $\begingroup$ If there is a decision procedure, we don't know how to find it. Otherwise you could ask "Is SAT in P?" and become very famous. Whether P vs NP can be solved either way in ZFC is still open afaik. $\endgroup$ – adrianN Aug 27 '17 at 8:06
  • 1
    $\begingroup$ Please note that P, NP, ... are classes of problems, not of algorithms. Algorithms do not lie in any of these classes. $\endgroup$ – Gregor Michalicek Aug 27 '17 at 8:08
  • $\begingroup$ There are polytime complete grammars. So in some sense P is decidable that way, but deciding if a Turing Machine is in P is another question. $\endgroup$ – DanielV Aug 27 '17 at 8:09
  • 2
    $\begingroup$ The usual rule is one question per post. $\endgroup$ – Yuval Filmus Aug 27 '17 at 8:19
  • 1
    $\begingroup$ @DanielV P is a class of languages, not a class of algorithms or Turing machines. There's no such thing as "a Turing machine... in P." $\endgroup$ – David Richerby Aug 27 '17 at 9:13
6
$\begingroup$

The following problem is undecidable:

Given an algorithm $A$, decide whether it runs in polynomial time.

Indeed, if you could decide this problem, then you could decide the halting problem, in the following way. Let $M$ be an input to the halting problem (we want to know whether $M$ halts on the empty input). Construct an algorithm $A$ which, on input $n$, runs $M$ for $n$ steps, and if $M$ halts, counts from $1$ to $2^n$. Then $M$ halts iff $A$ doesn't run in polynomial time.


You seem to be conflating several different meanings of decidable:

  1. Decidable by an algorithm.
  2. Can be proved or disproved.
  3. Is true or false.

It is meaningless to ask whether "P vs. NP" can be decided by an algorithm, since there's no input here. It is meaningful to ask whether "P vs. NP" is determined by the "axioms of mathematics" (say, ZFC) or not; see what Scott Aaronson has to say about it. Finally, in classical logic every statement is either true or false, and in particular either P=NP or P≠NP.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the charitable interpretation of my post. For question 1 regarding an algorithm whose runtime bounds are independent of ZFC, one could also use a modified $A$ from your proof to at least provide one which is not provable (in ZFC) to run in polynomial time: In step $n$, make $A$ check if there is a contradiction in the first $n$ enumerated consequences of the axioms of ZFC, and if yes, loop for $2^n$ steps. It will run in polynomial time iff ZFC is consistent. $\endgroup$ – heinzelotto Aug 28 '17 at 10:55
  • $\begingroup$ "Given an algorithm 𝐴, decide whether it runs in polynomial time"--is this semi-decidable? is it polytime verifiable? thanks! I assume if it reduces to the halting problem then yes to both since they are equivalent. $\endgroup$ – DeeDee Jun 20 at 1:46
  • $\begingroup$ Sounds like a rather difficult problem. $\endgroup$ – Yuval Filmus Jun 20 at 6:01
2
$\begingroup$
  1. P is a class of languages, not a class of algorithms. A language (or problem) is in P if there is some Turing machine that decides it in a polynomial number of steps. So, for example, determining whether a graph is connected is in P, since a TM can determine that efficiently. However, there are arbitrarily inefficient algorithms to determine connectivity: for example, an algorithm could waste time counting to $2^n$ before looking at the graph. If you want to know whether a particular algorithm runs in polynomial time, that is undecidable, as Yuval shows.

  2. No, because that isn't even a computational problem. Suppose that you wanted to design a Turing machine that determined if given languages were in P. What would the input to your Turing machine be? Remember – it has to be a finite string. Probably the closest you could get is to give a Turing machine as input and ask if the language accepted by that machine is in P (i.e., either the given TM decides the language in polynomial time or some other TM does). But that is undecidable for the same reasons as above.

  3. No because, again, that isn't a computational problem: it's something that's either true or false. In this case, there's no input at all.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ad 3: We can reasonably define $L = \{ x \in \{1\} \mid x=x \implies \mathrm{P} = \mathrm{NP} \}$ or a similar; $L = \emptyset$ if P != NP, and $L=\{1\}$ if P = NP. We don't know which, but $L$ is definitely decidable. (Which seems to confuse students of every generation.) $\endgroup$ – Raphael Aug 27 '17 at 20:21
  • 1
    $\begingroup$ Somehow I made the mistakes of a) restricting myself (without stating so) only to problems/languages that are Turing-decidable in the first place, and b) associating an algorithm with the language it decides and associating a decidable problem with the asymptotically fastest algorithm that decides it. Thank you, I wish I could accept your answer as well, since it correctly "answers" my confusion on a meta level. $\endgroup$ – heinzelotto Aug 28 '17 at 10:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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