3 ms·

Could P=NP be undecidable?

thomasahle 11y ago
Usually in math we talk about a statement being "independent", which means that it is compatible with the axioms for it to be true as well as false. If p=np were indeed independent, we could make it an axiom. Then we could do a complete search for a polynomial algorithm for 3sat, and we would be guaranteed to succeed. Since computing is somewhat a model of the physical world, something like this would surprise me. It seems like computing being modeled on the physical world, the model must contain the answer to the question. But who knows.
- mtdewcmu 11y ago
  p=np is a well-posed question, so clearly it must have an answer. We can't just make it an axiom. However, the thought occurred to me that perhaps p=np could reduce to some undecidable problem (in the halting problem-sense). In that case, solving p=np would be impossible. But we could prove that it's impossible, and the issue would be resolved. I'm not sure whether this scenario makes any sense. That's why I asked the question.
  - digama 11y ago
    Just because a question is well-posed doesn't mean it must be provable or disprovable. Consistency of ZFC is also a perfectly well-posed question with a finite answer (if one exists), but we know it is impossible to prove regardless. I don't think we can exclude independence as an option for any currently open question without actually proving or disproving it. (Of course, most mathematicians don't really think that P=NP will turn out to be independent, any more than the Riemann hypothesis or Goldbach's conjecture, but we don't know for sure.)
    - mtdewcmu 11y ago
      I'm trying to wrap my head around how P=NP could not have an answer, and I am not having much success. It could be that I am not educated enough to understand. Notwithstanding that, I don't see how any of this relates to my original question.
  - shotwell 11y ago
    You're misunderstanding something. P=NP is about whether two sets are equal. If it's "undecidable" or "independent", then ZFC is consistent with either P=NP or P \neq NP.
    - mtdewcmu 11y ago
      Independent doesn't sound like the same thing as undecidable. Given a program P, it is undecidable whether that program will halt. There is an answer: P either halts or it doesn't. There is just no way to find out (in general).
      - shotwell 11y ago
        Yes, 'undecidable' is used for a similar class of mathematical problems. For example, the continuum hypothesis - another question about an equality of sets - is undecidable in ZFC. This notion is strongly related to undecidability on Turing machines (possibly equivalent, depending on how you look at it).
      - johncolanduoni 11y ago
        They are intimately related. If you look at how Gödel's incompleteness theorem is stated, the existence of "effective procedures" (I.e. Computable functions) figures in intimately. A good overview of this in a reasonably accessible format can be found here: http://www.scottaaronson.com/blog/?p=710 http://www.scottaaronson.com/blog/?p=710 The same author wrote a good treatment of the implications of the undecidability of P=NP: http://www.scottaaronson.com/papers/pnp.pdf http://www.scottaaronson.com/papers/pnp.pdf Scott Aaronson is probably one of the best at explaining theoretical computer science, if you're interested in these topics you should follow his blog.
- digama 11y ago
  If P=NP is independent, then we already know that a complete search for a polynomial algorithm for 3SAT will fail (because if there were such an algorithm it would prove P=NP, so it wouldn't be independent). Adding P=NP as an axiom doesn't change this; instead it effectively augments the system with certain "nonstandard" natural numbers (which are larger than any concretely describable term but "look" like regular natural numbers from within the system), and this mythical polynomial algorithm for 3SAT will have nonstandard length (meaning for pratical purposes that it is infinitely long).
  - repsilat 11y ago
    > If P=NP is independent, then we already know that a complete search for a polynomial algorithm for 3SAT will fail A search for a provably polynomial algorithm will fail, but that doesn't mean that an unprovably polynomial time algorithm couldn't exist. We might come up with strong arguments for why a particular algorithm would be polynomial in practice. Still, I'd say "independent but false" is more likely than "independent but true."

Usually in math we talk about a statement being "independent", which means that it is compatible with the axioms for it to be true as well as false. If p=np were indeed independent, we could make it an axiom. Then we could do a complete search for a polynomial algorithm for 3sat, and we would be guaranteed to succeed. Since computing is somewhat a model of the physical world, something like this would surprise me. It seems like computing being modeled on the physical world, the model must contain the answer to the question. But who knows.

mtdewcmu 11y ago
p=np is a well-posed question, so clearly it must have an answer. We can't just make it an axiom. However, the thought occurred to me that perhaps p=np could reduce to some undecidable problem (in the halting problem-sense). In that case, solving p=np would be impossible. But we could prove that it's impossible, and the issue would be resolved. I'm not sure whether this scenario makes any sense. That's why I asked the question.
- digama 11y ago
  Just because a question is well-posed doesn't mean it must be provable or disprovable. Consistency of ZFC is also a perfectly well-posed question with a finite answer (if one exists), but we know it is impossible to prove regardless. I don't think we can exclude independence as an option for any currently open question without actually proving or disproving it. (Of course, most mathematicians don't really think that P=NP will turn out to be independent, any more than the Riemann hypothesis or Goldbach's conjecture, but we don't know for sure.)
  - mtdewcmu 11y ago
    I'm trying to wrap my head around how P=NP could not have an answer, and I am not having much success. It could be that I am not educated enough to understand. Notwithstanding that, I don't see how any of this relates to my original question.
- shotwell 11y ago
  You're misunderstanding something. P=NP is about whether two sets are equal. If it's "undecidable" or "independent", then ZFC is consistent with either P=NP or P \neq NP.
  - mtdewcmu 11y ago
    Independent doesn't sound like the same thing as undecidable. Given a program P, it is undecidable whether that program will halt. There is an answer: P either halts or it doesn't. There is just no way to find out (in general).
    - shotwell 11y ago
      Yes, 'undecidable' is used for a similar class of mathematical problems. For example, the continuum hypothesis - another question about an equality of sets - is undecidable in ZFC. This notion is strongly related to undecidability on Turing machines (possibly equivalent, depending on how you look at it).
    - johncolanduoni 11y ago
      They are intimately related. If you look at how Gödel's incompleteness theorem is stated, the existence of "effective procedures" (I.e. Computable functions) figures in intimately. A good overview of this in a reasonably accessible format can be found here: http://www.scottaaronson.com/blog/?p=710 http://www.scottaaronson.com/blog/?p=710 The same author wrote a good treatment of the implications of the undecidability of P=NP: http://www.scottaaronson.com/papers/pnp.pdf http://www.scottaaronson.com/papers/pnp.pdf Scott Aaronson is probably one of the best at explaining theoretical computer science, if you're interested in these topics you should follow his blog.
digama 11y ago
If P=NP is independent, then we already know that a complete search for a polynomial algorithm for 3SAT will fail (because if there were such an algorithm it would prove P=NP, so it wouldn't be independent). Adding P=NP as an axiom doesn't change this; instead it effectively augments the system with certain "nonstandard" natural numbers (which are larger than any concretely describable term but "look" like regular natural numbers from within the system), and this mythical polynomial algorithm for 3SAT will have nonstandard length (meaning for pratical purposes that it is infinitely long).
- repsilat 11y ago
  > If P=NP is independent, then we already know that a complete search for a polynomial algorithm for 3SAT will fail A search for a provably polynomial algorithm will fail, but that doesn't mean that an unprovably polynomial time algorithm couldn't exist. We might come up with strong arguments for why a particular algorithm would be polynomial in practice. Still, I'd say "independent but false" is more likely than "independent but true."