Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
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.