HackerPapers

arXiv:quant-ph/0502072quant-ph

NP-complete Problems and Physical Reality

Scott Aaronson

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.

arXiv comments
23 pages, minor corrections
Journal reference
ACM SIGACT News, March 2005
DOI
Subjects
quant-phQuantum Physics cs.CCComputational Complexity gr-qcGeneral Relativity and Quantum Cosmology

On Hacker News

Linked by 12 identifiable commenters in 12 comments across 11 threads, from Aug 2010 to Aug 2023. Found in 5 HN submissions from Dec 2011 to Nov 2016. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments11 threads

  1. Thermodynamic Linear Algebra 1 comment

    • https://arxiv.org/abs/quant-ph/0502072 Your comment reminded me of this classic of the genre. An extremely approachable read.

      hiddencostView on HNParent context

  2. I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA 1 comment

    • Yup. :-) Or better yet, we could bifurcate into: (1) Why is our universe apparently unable to solve the halting problem for Turing machines? The answer, presumably, is a combination of the physical Church-Turing Thesis (specifically, the apparent impossibility of…

      ScottAaronsonView on HNParent context

  3. Ask HN: What is your favorite CS paper? 1 comment

    • "NP-complete Problems and Physical Reality" by Scott Aaronson. It relates NP-complete problems to examples in nature. Excellent paper and a fun read. https://arxiv.org/abs/quant-ph/0502072

      RickasaurusView on HNParent context

  4. The P=?NP Poll (2002) [pdf] 2 comments
  5. A bad citizen in Javaland (2006) 1 comment

    • Related (amazing) paper by Scott Aaronson: "NP-complete Problems and Physical Reality" (http://arxiv.org/abs/quant-ph/0502072). He proposes "anthropic computing" as a way of solving NP-complete problems in polynomial time: guess an answer, then kill yourself if the answer is…

      evanpwView on HNParent context

  6. Computability: The Greatest Law of Physics 1 comment

    • Reminds me of http://arxiv.org/abs/quant-ph/0502072 Also, as a Physicist and Computer Scientist, it explains my uneasiness when existence claims are made regarding infinite objects. For example, we can describe the trajectory of a particle using Feynman path integrals, which…

      chriswarboView on HNParent context

  7. An Argument for P=NP (2005) [pdf] 1 comment

    • OK, it says this: For example, the Steiner Tree problem (STP) is known to be NP-complete ... Nonetheless, a simple physical process (termed an analog computation) can apparently solve it quickly. No, it can't. Small, trivial cases can be solved, but I believe it's been shown…

      ColinWrightView on HNParent context

  8. Physical Limits to Computation (2000) [pdf] 1 comment
  9. Is Quantum Mechanics an Island in Theoryspace? (2004) [pdf] 1 comment

    • This is a good follow up read to the classic "NP-complete Problems and Physical Reality"[1] and has not been discussed here. [1] http://arxiv.org/pdf/quant-ph/0502072v2.pdf

      weinzierlView on HNParent context

  10. Using A Slime-Mold To Calculate Minimum Spanning Trees 1 comment

    • Only for sufficiently small definitions of "solve": http://arxiv.org/pdf/quant-ph/0502072v2 Definitions which turn out to be very small indeed.

      jerfView on HNParent context

  11. Ask HN: If P = NP, what does it mean? 1 comment

    • This paper http://arxiv.org/pdf/quant-ph/0502072 explores what it means for physical reality. It's really interesting. There are many possible scenarios, however. This blog post http://rjlipton.wordpress.com/2009/07/03/is-pnp-an-ill-posed... describes some of them.

      alextpView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.