NP-complete Problems and Physical Reality
<|reference_start|>NP-complete Problems and Physical Reality: 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.<|reference_end|>
@article{aaronson2005np-complete,
    title={NP-complete Problems and Physical Reality},
    author={Scott Aaronson},
    journal={ACM SIGACT News, March 2005},
    year={2005},
    archivePrefix={arXiv},
    eprint={quant-ph/0502072},
    primaryClass={quant-ph cs.CC gr-qc}
}