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

[Computational Complexity] NP-complete Problems and Physical Reality

Expand Messages
  • Lance
    Scott Aaronson has a fun paper in the complexity column of the new SIGACT News where he addresses the question: Can NP-complete problems be solved efficiently
    Message 1 of 1 , Mar 9, 2005
    • 0 Attachment
      Scott Aaronson has a fun paper in the complexity column of the new SIGACT News where he addresses the question: Can NP-complete problems be solved efficiently in the physical universe? Worth reading though I can sum up the answer in one word: No.

      --
      Posted by Lance to Computational Complexity at 3/9/2005 06:42:00 PM
    Your message has been successfully submitted and would be delivered to recipients shortly.