Re:Is P=NP an Ill Posed Problem?
by miloshh on Friday July 03, 2009 @02:58PM
(#686464)
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.
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.