NP-complete Problems and Physical Reality

Simple item page
dc.creatorAaronson, Scott
dc.date2005-02-12
dc.date2005-02-21
dc.date.accessioned2026-07-07T06:12:09Z
dc.date.available2026-07-07T06:12:09Z
dc.descriptionCan 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.
dc.description23 pages, minor corrections
dc.identifierhttps://arxiv.org/abs/quant-ph/0502072
dc.identifierhttp://arxiv.org/abs/quant-ph/0502072
dc.identifierACM SIGACT News, March 2005
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/92704
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.subjectGeneral Relativity and Quantum Cosmology
dc.titleNP-complete Problems and Physical Reality
dc.typetext

Files

Collections

arXiv