NP-complete Problems and Physical Reality Export

@misc{citeulike:95939, 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.}, archivePrefix = {arXiv}, author = {Aaronson, Scott}, citeulike-article-id = {95939}, citeulike-linkout-0 = {http://arxiv.org/abs/quant-ph/0502072}, citeulike-linkout-1 = {http://arxiv.org/pdf/quant-ph/0502072}, day = {12}, eprint = {quant-ph/0502072}, keywords = {np-complete, problems}, month = {February}, posted-at = {2005-02-15 17:42:28}, priority = {2}, title = {NP-complete Problems and Physical Reality}, url = {http://arxiv.org/abs/quant-ph/0502072}, year = {2005} }

TY - ELEC ID - citeulike:95939 L3 - citeulike-article-id:95939 N2 - 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. TI - NP-complete Problems and Physical Reality KW - np-complete KW - problems AU - Aaronson, Scott PY - 2005/02/12/ UR - http://arxiv.org/abs/quant-ph/0502072 ER -