Thursday, March 27, 2003

Is P versus NP undecidable?

Haipeng Guo asks "Is is possible that the P vs NP problem is undecidable? Is there any paper talking about this?"

Short Answer: Until we have a proof that P≠NP or a proof that P=NP, we cannot rule out the possibility that the P versus NP question is not provable in one of the standard logical theories. However, I firmly believe there exists a proof that P≠NP. To think that the question is not provable just because we are not smart enough to prove it is a cop-out.

You'll have to be patient for the long answer. The October 2003 BEATCS Complexity Column will be devoted to this topic.

No comments:

Post a Comment