4 ms·

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 r

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

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.