This work is licensed under a
Creative Commons License.
|
Thursday, March 27, 2003
Is P versus NP undecidable?
Posted by Lance
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.
6:23 AM
# 0 comments
Links to this post:
Weblog Home
Archives
