[My Computational Complexity Web Log] 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.
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/27/2003 7:23:22 AM
Powered by Blogger Pro