NP-complete Problems and Physical Reality

Details NP-complete Problems and Physical Reality NP-complete Problems and Physical Reality

2005-02-12

arxiv.org/abs/quant-ph/0502072v2

ACM SIGACT News, March 2005

Physics

Quantum Physics

23 pages, minor corrections

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

NP-complete Problems and Physical Reality does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with NP-complete Problems and Physical Reality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and NP-complete Problems and Physical Reality will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-543825