Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Is P versus NP undecidable?

Expand Messages
  • Lance Fortnow
    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 PNP
    Message 1 of 1 , Mar 27, 2003
    • 0 Attachment
      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

    Your message has been successfully submitted and would be delivered to recipients shortly.