Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-026 | 15th February 2005 00:00

NP-complete Problems and Physical Reality

RSS-Feed




TR05-026
Authors: Scott Aaronson
Publication: 1st March 2005 00:14
Downloads: 5773
Keywords: 


Abstract:

Can NP-complete problems be solved efficiently in the physical universe?
I survey proposals including soap bubbles, protein folding, quantum
computing, quantum advice, quantum adiabatic algorithms,
quantum-mechanical nonlinearities, hidden variables, relativistic time
dilation, analog computing, Malament-Hogarth spacetimes, quantum
gravity, closed timelike curves, and "anthropic computing." The section
on soap bubbles even includes some "experimental" results. While I do
not believe that any of the proposals will let us solve NP-complete
problems efficiently, I argue that by studying them, we can learn
something not only about computation but also about physics.



ISSN 1433-8092 | Imprint