6 ms·

NP-Complete Problems and Physical Reality (2005)

88 points by andyjohnson0 11y ago

kenny-log_ins 11y ago
If you enjoyed this I highly recommend both his book, "Quantum Computing Since Democritus", and blog (http://www.scottaaronson.com/blog/ http://www.scottaaronson.com/blog/). Tagline of the blog is "If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once."
- _asummers 11y ago
  Wholeheartedly recommend this book as well. He gives a brief overview of classical complexity, how quantum matrices work, then how quantum complexity works. It's really accessible to those with some complexity background.
- andyjohnson0 11y ago
  Detailed notes and problem sets for a series of twenty-one(!) lectures based on the book are at [1]. [1] http://www.scottaaronson.com/democritus/ http://www.scottaaronson.com/democritus/
nafets 11y ago
I remember a TED talk on the failed attempts to find cases in which nature solves a NP-complete problem. Paper must be an interesting read.
- seiji 11y ago
  This one is always fun: https://www.youtube.com/watch?v=mvBSkt6LhJE https://www.youtube.com/watch?v=mvBSkt6LhJE Related: http://www.wired.com/2010/01/slime-mold-grows-network-just-like-tokyo-rail-system/ http://www.wired.com/2010/01/slime-mold-grows-network-just-l...
dsfsdfd 11y ago
"But another reason we believe P≠NP is that otherwise mathematical creativity could be automated!" I have a problem with this. Just because the thought is unpleasant does not make it true or false. Besides, perhaps this is the very difference between automation and intelligence, perhaps the point at which you can ask this of a computer is the point at which you should no longer consider it a computer.
- c_lebesgue 11y ago
  Sure, it is certainly possible that mathematics can be automated, but mathematics is also over 2000 years old. We are not much closer to automating it than the Greeks were. P=NP does not only break the Complexity theory (which is a relatively new invention), it also has profound consequences to all of human reasoning.
  - TheOtherHobbes 11y ago
    We already have commoditised math solvers for any number of (relatively) trivial problems. What we haven't automated is mathematical creativity, which is a completely different class of problem.
    - foobar2020 11y ago
      The whole difficulty of the hard complexity questions such as "Is P=NP?" hides in the non-trivial, "corner" cases. Sure, we have SAT solvers that are by many practical standards really good. P=NP would imply that we can relatively easily find polynomially long proofs to many hard propositions, such as the P=NP problem itself! Or many other open mathematical problems. Creativity is an anthropomorphic, abstract concept, a way of describing human ways to find solutions. What really matters is the proofs.
- drd0rk 11y ago
  Or you should no longer consider yourself something else than a computer.
- bane 11y ago
FeepingCreature 11y ago
On the point of anthropic computing: it is important to note that you have not accomplished any _improvement_ to your condition by killing yourself; before as after, you had found a correct solution with probability 2^-n. Anthropic computing is just "fancy guessing". What is interesting about it to me is that the "true computational nature of reality" must be such that sufficient computation is available for you to run the _validation_ of your solution in logarithmic time an exponential number of times ("in parallel"), because otherwise you could not find yourself _at all_ in a universe where you knew you had found the correct computation. Which does make it strange that quantum physics does not seem to give us any way to "get at" all this computation that must be going on behind the scenes. (Unless the "true nature" of reality is such that a subset of the wavefunction is being computed "for cheap". Collapse exonerated?)
- andyjohnson0 11y ago
  By running the validation "in parallel", do you mean running it in each of the possible quantum "many worlds" in which validation takes place? If so, aren't you implicitly assuming that these other parallel worlds somehow draw on a shared pool of computing resource? This might be true [1], but equally there may not be a "behind the scenes" of reality at all. [1] How would we know? Run a timing attack on the underlying compute infrastructure?
  - kordless 11y ago
    I'm leaning toward the parallel universe hypothesis as well, except I'm thinking it's more like there are part-time processes that run in parallel, do their work, then exit after they come to some type of consensus of state. It would end up looking something like a bunch of containers running a game on your computer, processing all the other player's moves, arriving at consensus, sending that consensus to a central 'compute' spot where a global consensus took place, wait for a reply, then take what the global central thing said was a valid state of things. Rinse and repeat. Stick it all in blockchain in case there's a disagreement. I keep pointing out to people I can't make their beers (including glass) disappear while we're talking at a table. That this universe doesn't allow me to hack it (and presumably keeps others from hacking it) is a nice feature.
andyjohnson0 11y ago
I posted this link because (a) it seemed like a good survey of the subject, and (b) I felt like I almost understood most of it. Does anyone have any suggestions for accessible further reading at the intersection of computer science and physics?
- giech 11y ago
  His Philosophy-Complexity paper is also fantastic, in case you have not read it already: http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf It has also been discussed most recently here: https://news.ycombinator.com/item?id=9061744 https://news.ycombinator.com/item?id=9061744
  - andyjohnson0 11y ago
    Thanks. I'll definitely be reading those. Aaronson's talk on Computational Complexity and the Anthropic Principle [1] also looks interesting. [1] http://www.scottaaronson.com/talks/anthropic.html http://www.scottaaronson.com/talks/anthropic.html
sqrt17 11y ago
A point that has become more obvious over the years is this: there are "soft" instances of NP-complete problems where you can find good approximations in reasonable time, and there are "crunchy" instances of the same class of problem where you don't find a good approximation. Commercial ILP solvers (e.g. Gurobi, CPlex) profit from the fact that quite often it is possible to formulate NP-complete problems and find good solutions in acceptable time. Similarly, many of the "physical" ways of solving NP-complete problems work ok for easy instances and get unwieldly fast if confronted with difficult instances.
a1b2c3 11y ago
From 2005
sudioStudio64 11y ago
I'm looking forward to his take on the recent thing about memristor machines being able to solve NP-complete problems...it was on HN a couple of days ago.
amatus 11y ago
"If some physicist wants to continue the tradition of naming quantum gravity theories using monosyllabic words for elongated objects that mean something completely different in computer science, then I propose the most revolutionary advance yet: thread theory."

88 points by andyjohnson0 11y ago

If you enjoyed this I highly recommend both his book, "Quantum Computing Since Democritus", and blog (http://www.scottaaronson.com/blog/ http://www.scottaaronson.com/blog/). Tagline of the blog is "If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once."

_asummers 11y ago
Wholeheartedly recommend this book as well. He gives a brief overview of classical complexity, how quantum matrices work, then how quantum complexity works. It's really accessible to those with some complexity background.
andyjohnson0 11y ago
Detailed notes and problem sets for a series of twenty-one(!) lectures based on the book are at [1]. [1] http://www.scottaaronson.com/democritus/ http://www.scottaaronson.com/democritus/

nafets 11y ago

I remember a TED talk on the failed attempts to find cases in which nature solves a NP-complete problem. Paper must be an interesting read.

seiji 11y ago
This one is always fun: https://www.youtube.com/watch?v=mvBSkt6LhJE https://www.youtube.com/watch?v=mvBSkt6LhJE Related: http://www.wired.com/2010/01/slime-mold-grows-network-just-like-tokyo-rail-system/ http://www.wired.com/2010/01/slime-mold-grows-network-just-l...

dsfsdfd 11y ago

"But another reason we believe P≠NP is that otherwise mathematical creativity could be automated!" I have a problem with this. Just because the thought is unpleasant does not make it true or false. Besides, perhaps this is the very difference between automation and intelligence, perhaps the point at which you can ask this of a computer is the point at which you should no longer consider it a computer.

c_lebesgue 11y ago
Sure, it is certainly possible that mathematics can be automated, but mathematics is also over 2000 years old. We are not much closer to automating it than the Greeks were. P=NP does not only break the Complexity theory (which is a relatively new invention), it also has profound consequences to all of human reasoning.
- TheOtherHobbes 11y ago
  We already have commoditised math solvers for any number of (relatively) trivial problems. What we haven't automated is mathematical creativity, which is a completely different class of problem.
  - foobar2020 11y ago
    The whole difficulty of the hard complexity questions such as "Is P=NP?" hides in the non-trivial, "corner" cases. Sure, we have SAT solvers that are by many practical standards really good. P=NP would imply that we can relatively easily find polynomially long proofs to many hard propositions, such as the P=NP problem itself! Or many other open mathematical problems. Creativity is an anthropomorphic, abstract concept, a way of describing human ways to find solutions. What really matters is the proofs.
drd0rk 11y ago
Or you should no longer consider yourself something else than a computer.
bane 11y ago

FeepingCreature 11y ago

On the point of anthropic computing: it is important to note that you have not accomplished any _improvement_ to your condition by killing yourself; before as after, you had found a correct solution with probability 2^-n. Anthropic computing is just "fancy guessing". What is interesting about it to me is that the "true computational nature of reality" must be such that sufficient computation is available for you to run the _validation_ of your solution in logarithmic time an exponential number of times ("in parallel"), because otherwise you could not find yourself _at all_ in a universe where you knew you had found the correct computation. Which does make it strange that quantum physics does not seem to give us any way to "get at" all this computation that must be going on behind the scenes. (Unless the "true nature" of reality is such that a subset of the wavefunction is being computed "for cheap". Collapse exonerated?)

andyjohnson0 11y ago
By running the validation "in parallel", do you mean running it in each of the possible quantum "many worlds" in which validation takes place? If so, aren't you implicitly assuming that these other parallel worlds somehow draw on a shared pool of computing resource? This might be true [1], but equally there may not be a "behind the scenes" of reality at all. [1] How would we know? Run a timing attack on the underlying compute infrastructure?
- kordless 11y ago
  I'm leaning toward the parallel universe hypothesis as well, except I'm thinking it's more like there are part-time processes that run in parallel, do their work, then exit after they come to some type of consensus of state. It would end up looking something like a bunch of containers running a game on your computer, processing all the other player's moves, arriving at consensus, sending that consensus to a central 'compute' spot where a global consensus took place, wait for a reply, then take what the global central thing said was a valid state of things. Rinse and repeat. Stick it all in blockchain in case there's a disagreement. I keep pointing out to people I can't make their beers (including glass) disappear while we're talking at a table. That this universe doesn't allow me to hack it (and presumably keeps others from hacking it) is a nice feature.

andyjohnson0 11y ago

I posted this link because (a) it seemed like a good survey of the subject, and (b) I felt like I almost understood most of it. Does anyone have any suggestions for accessible further reading at the intersection of computer science and physics?

giech 11y ago
His Philosophy-Complexity paper is also fantastic, in case you have not read it already: http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf It has also been discussed most recently here: https://news.ycombinator.com/item?id=9061744 https://news.ycombinator.com/item?id=9061744
- andyjohnson0 11y ago
  Thanks. I'll definitely be reading those. Aaronson's talk on Computational Complexity and the Anthropic Principle [1] also looks interesting. [1] http://www.scottaaronson.com/talks/anthropic.html http://www.scottaaronson.com/talks/anthropic.html

sqrt17 11y ago

A point that has become more obvious over the years is this: there are "soft" instances of NP-complete problems where you can find good approximations in reasonable time, and there are "crunchy" instances of the same class of problem where you don't find a good approximation. Commercial ILP solvers (e.g. Gurobi, CPlex) profit from the fact that quite often it is possible to formulate NP-complete problems and find good solutions in acceptable time. Similarly, many of the "physical" ways of solving NP-complete problems work ok for easy instances and get unwieldly fast if confronted with difficult instances.

a1b2c3 11y ago

From 2005

sudioStudio64 11y ago

I'm looking forward to his take on the recent thing about memristor machines being able to solve NP-complete problems...it was on HN a couple of days ago.

amatus 11y ago

"If some physicist wants to continue the tradition of naming quantum gravity theories using monosyllabic words for elongated objects that mean something completely different in computer science, then I propose the most revolutionary advance yet: thread theory."