Skip to content
The methodOpen data
Back to the collection

NP-complete Problems and Physical Reality

Scott Aaronson

2005 · arXiv

PhysicsAlgorithmsBiology & medicine
Read the paper
HN score
1.5
Mentions
9
Readers
9
Months
9
What’s in a score?

From the 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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

9 selected excerpts · 9 total mentions

ScottAaronson
Neutral mention · rule
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 Turing-uncomputable processes in our world), with Church and Turing and Post's theorem on the unsolvability of the halting problem. Of course one could then push back and ask why the Church-Turing Thesis should be true of our world: i.e., why shouldn't there be physical "hypercomputers"? That's an enormous question, but my old survey "NP-Complete Problems and Physical Reality" contains some thoughts about it:…
Read the full comment
https://arxiv.org/abs/quant-ph/0502072 And then there's: (2) Why should we live in a universe that's unable to solve "its own" halting problem? I.e., even if super-Turing computers were physically possible, we could presumably formulate a halting problem for those computers, which would then require a still more powerful computer to solve (a super-duper-Turing computer?), and so on forever. This is because we could simply repeat Turing's diagonalization argument at a higher-level up -- given very minimal properties of computation, such as the ability to feed one program to another program as code, the ability of one program to emulate another one, and the ability to compute the NOT function. Once you have those properties, the inability of any given computational model (even a super-Turing model) to solve its own halting problem is just a matter of logic, as schoen said.
Original comment I'm Scott Aaronson, quantum computing/computational complexity researcher. AMA
evanpw
Neutral mention · rule
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 wrong.
Original comment A bad citizen in Javaland (2006)
chriswarbo
Neutral mention · rule
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 involve infinite sums over all possible paths. That's fine. Some will then treat this as a mechanism, i.e. claim that the reason particles have the trajectories they do, is because they literally are taking every possible path at once. This kind of reasoning sets my off my CS alarm bells, and articles like this provide justification for that. To see why this leap of reasoning is flawed, consider the…
Read the full comment
fact that we don't solve integrals by summing up an infinite number of infinitesimal quantities. To say that a human writing out a sequence of symbolic manipulations on a page literally is performing an infinite amount of computation is clearly false. I think Computer Scientists are much more comfortable than Physicists with considering the role of calculation in a theory; i.e. in Physics, the calculations we perform about a system are utterly distinct from that system: whether those calculations are easy or hard says nothing about what the system is doing (e.g. we can easily calculate path integrals, which particles "solve" using an infinite amount of brute-force); the only physically-relevant details are the values. In CS, we focus on the performance of calculations; we cannot claim that a system behaves over time in some way unless we can show that calculating that behaviour can be done in that time.
Original comment Computability: The Greatest Law of Physics
ColinWright
Neutral mention · rule
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 that when you get to mildly interesting cases it's just as likely to find non-optimal solutions, and sometimes even more likely to find non-optimal solutions. This is at the top of page 2, and it doesn't bode at all well. Section 3 of Aaronson's paper[0] discusses this explicitly, and comes to the conclusion that, not to put too fine a point on it, it doesn't work. In essence, looks like complete nonsense to me. [0] http://arxiv.org/pdf/quant-ph/0502072v2.pdf
Original comment An Argument for P=NP (2005) [pdf]
alextp
Neutral mention · rule
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.
Original comment Ask HN: If P = NP, what does it mean?

Keep following the thread.

More in Physics

More from the same topics.