5 ms·

> Can all interesting proofs be built with human-friendly steps? Maybe that's why we haven't worked out P and NP. P and NP is a very interesting case, since th

> Can all interesting proofs be built with human-friendly steps? Maybe that's why we haven't worked out P and NP. P and NP is a very interesting case, since there has been some meta-mathematical results that attempt to rule out certain methods of proof as being capable of producing a proof of it[1]. However, I don't think we have a good characterization of "human-friendly steps" that we could conceivably use to rule out the existence of such a proof completely. [1]: https://en.wikipedia.org/wiki/Natural_proof https://en.wikipedia.org/wiki/Natural_proof

rtkwe 11y ago
Even people can't always produce human friendly proofs. There's Shinichi Mochizuki who might have proven the ABC conjecture but no one can confirm it because he created a whole method and set of techniques/theories that no one else really gets. This is a person creating a branch so dense that it's taken 3 years and we still haven't determined if it's wrong. There's also the controversial Computer Assisted Proof. Which I think is a lesser version of completely computer generated proofs where there's the question of procedural errors and the difficulty of checking for them. https://en.wikipedia.org/wiki/Computer-assisted_proof https://en.wikipedia.org/wiki/Computer-assisted_proof
mtdewcmu 11y ago
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).

rtkwe 11y ago

Even people can't always produce human friendly proofs. There's Shinichi Mochizuki who might have proven the ABC conjecture but no one can confirm it because he created a whole method and set of techniques/theories that no one else really gets. This is a person creating a branch so dense that it's taken 3 years and we still haven't determined if it's wrong. There's also the controversial Computer Assisted Proof. Which I think is a lesser version of completely computer generated proofs where there's the question of procedural errors and the difficulty of checking for them. https://en.wikipedia.org/wiki/Computer-assisted_proof https://en.wikipedia.org/wiki/Computer-assisted_proof

mtdewcmu 11y ago

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).