Wednesday, March 09, 2005

NP-complete Problems and Physical Reality

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.

No comments:

Post a Comment