2005/02/12 by Scott Aaronson · 8 voices · 7 citations
Computer Science · Physics and Astronomy · #cs.CC #gr-qc #quant-ph
published as ACM SIGACT News, March 2005 · 23 pages, minor corrections
arxiv created 2005/02/21 · arxiv updated 2009/12/01
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.