7 ms·

I once heard Manuel Blum say that it could be shown that the result can be neither proven nor disproven given our framework of mathematics, similar to the Conti

I once heard Manuel Blum say that it could be shown that the result can be neither proven nor disproven given our framework of mathematics, similar to the Continuum Hypothesis. In this case, I would call P=NP an ill-posed problem. I think the OP makes great points in his article, but the title of the blog post is wrong. He really speaks of how the scope of P=NP is misconceived by most people.

miloshh 17y ago
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 - no middle-ground here. But I agree, the blog isn't about this issue at all.
- 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]
jerf 17y ago
The problem is that if it can be proved that P=NP can't be proved or disproved, that constitutes a proof that P!=NP, since it proves that you won't ever come up with an algorithm, which is what the question is really about in the first place. This being math, one can imagine ever more finely sliced arguments being made, but a "simple" proof that P=NP is forever unsolvable is itself a proof ("the probability that we will find such an algorith is 1 in 10^100"), for all practical and most theoretical (though not all) purposes.
- mitko 17y ago
  This comment shows you don't know the definition of the problem. The P?=NP problem is defined in such a way that it is either true or not. P- the set of languages that can be recognized by Deterministic Turing Machine in O(n^k) for some fixed k, n-length of input. NP - the set of languages that can be recognized by NON-Deterministic Turing Machine in O(n^k) for some fixed k, n-length of input.
  - scscsc 17y ago
    Your comment shows you don't know much about logic.
    - mitko 17y ago
      No it doesn't! Justify your claim. I just stated the definition of the P?=NP problem. You can find it in any good book on complexity theory. For example: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X http://www.amazon.com/Introduction-Theory-Computation-Michae...
      - scscsc 17y ago
        I was not refering to your definition of P and NP (which I've just reread and I think it's not good; you want "accept", not "recognize"). I was refering to the fact that you do not make the difference between "true" and "provable", which can be found in any standard introductory book on logic; or, if you prefer a novel, Hofstadter's Goedel, Escher, Bach: an Eternal Golden Braid.

miloshh 17y ago

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 - no middle-ground here. But I agree, the blog isn't about this issue at all.

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]

jerf 17y ago

The problem is that if it can be proved that P=NP can't be proved or disproved, that constitutes a proof that P!=NP, since it proves that you won't ever come up with an algorithm, which is what the question is really about in the first place. This being math, one can imagine ever more finely sliced arguments being made, but a "simple" proof that P=NP is forever unsolvable is itself a proof ("the probability that we will find such an algorith is 1 in 10^100"), for all practical and most theoretical (though not all) purposes.

mitko 17y ago
This comment shows you don't know the definition of the problem. The P?=NP problem is defined in such a way that it is either true or not. P- the set of languages that can be recognized by Deterministic Turing Machine in O(n^k) for some fixed k, n-length of input. NP - the set of languages that can be recognized by NON-Deterministic Turing Machine in O(n^k) for some fixed k, n-length of input.
- scscsc 17y ago
  Your comment shows you don't know much about logic.
  - mitko 17y ago
    No it doesn't! Justify your claim. I just stated the definition of the P?=NP problem. You can find it in any good book on complexity theory. For example: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/053494728X http://www.amazon.com/Introduction-Theory-Computation-Michae...
    - scscsc 17y ago
      I was not refering to your definition of P and NP (which I've just reread and I think it's not good; you want "accept", not "recognize"). I was refering to the fact that you do not make the difference between "true" and "provable", which can be found in any standard introductory book on logic; or, if you prefer a novel, Hofstadter's Goedel, Escher, Bach: an Eternal Golden Braid.