4 ms·

Well, even if a given logical theory cannot decide P=NP, it is still a well-posed problem. Either there is a polynomial-time algorithm for SAT or there isn't -

• jganetsk 17y ago
  Either there is a polynomial-time algorithm for SAT or there isn't - no middle-ground here. Statement of the continuum hypothesis: There is no set whose cardinality is strictly between that of the integers and that of the real numbers. You can provide your argument against the continuum hypothesis. No middle ground? There might not be a polynomial-time algorithm for SAT... but how would we know? You might not be able to prove that one does not exist. The absence of evidence is not the evidence of absence. And we could be eternally locked in this state. Middle ground exists, for constructivists, those who don't admit the law of the excluded middle (that any statement must be either true or false). And I think most theoretical computer scientists are of this persuasion.
  • miloshh 17y ago
    OK, I see what you mean, but I would argue that P=NP is a question of a very different nature than CH. CH is a statement about the existence of an abstract infinite set, so it is not that surprising that its truth depends on your very definition of a set, an elusive object with multiple possible meanings. On the other hand, P=NP is a statement about boolean formulas, Turing machines and polynomials. None of these are elusive, they are very cleanly defined, trivial concepts. So it's a very well-posed question. Of course, we could still not be able to prove the (non)existence of a polynomial algorithm for SAT in ZF set theory. In that case, too bad for ZF, but whether P=NP is still a meaningful question.
    • deleted 17y ago
      [deleted]