4 ms·

NP-complete Problems and Physical Reality (2005)

94 points by wfunction 12y ago

xnull2guest 12y ago
This is classic Scott Aaronson - in fact, he's suggested on more than one occasion that we should adopt 'NP-hard problems are infeasible for the physical universe to solve' as a law of thermodynamics, arguing that the evidence for this is at least as good as other laws and that a disproof of this would be just as revolutionary. Other Aaronson classics include "Who can name the bigger number?" [1], "Shor, I'll do it" (his layman's explanation of Shor's algorithm for finding hidden abelian subgroups) [2], "Is Quantum Mechanics An Island In Theoryspace?" [3], and his blog turned class turned book "Quantum Computing Since Democritus" [4]. But really there's a ton of gold. He has a really neat explanation of the AKS primality testing algorithm [5] and modeled an imaginary easier-to-build (?) less-powerful-but-probably-more-powerful-than-classic-computers computing machine based on the quantum effects of light [6]. In general his blog tends to accumulate a lot of drama and controversy in its comments (because Prof. Aaronson is very opinionated), which he handles very hilariously. It's worth following him over at Shtetl-Optimized [7]. MIT was smart to have given him tenure. [1] http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html [2] http://www.scottaaronson.com/blog/?p=208 http://www.scottaaronson.com/blog/?p=208 [3] http://www.scottaaronson.com/papers/island.pdf http://www.scottaaronson.com/papers/island.pdf [4] http://www.scottaaronson.com/democritus/ http://www.scottaaronson.com/democritus/ [5] http://www.scottaaronson.com/writings/prime.pdf http://www.scottaaronson.com/writings/prime.pdf [6] http://www.scottaaronson.com/papers/optics.pdf http://www.scottaaronson.com/papers/optics.pdf [7] http://www.scottaaronson.com/blog/ http://www.scottaaronson.com/blog/
- deleted 12y ago
  [deleted]
- scottlocklin 12y ago
  Aaronson has a gift for popularization, but the fact of the matter is, mathematicians can be astoundingly impractical. Practically speaking, NP hard problems are solved constantly, at least in an approximate sense, by physical reality and computer algorithms; soap bubbles, chemical dynamics, airline scheduling. The exact solution to any problem is uninteresting, just as the exact value of a real number is uninteresting.
  - xnull2guest 12y ago
    Scott Aaronson I think himself would agree, as do I. He has some legitimate counterpoints though too on NP-Hard problems being solved. He points out the canonical instance of such problems "folding protein" (chemical dynamics) can not really count, as proteins that misfold (pryons) are in extremely dangerous molecules: evolution has heavily selected to find proteins that it can fold quickly and reliably. He'll also point out that rocks don't find global minimums - that there are in fact a plethora of these examples. He tests soap bubbles and finds many 'easy' instances where it fail. Namely, he's responded to that criticism countless times - once with an actual physical experiment (the paper itself announces). It very likely is interesting to see to what degree other physical processes can approximately compute otherwise hard problems. It's just not fair to pick Aaronson to do it; he himself would be the first to admit that it isn't his area and that you'd want someone like Champagne to do it. In summary, yeah definitely his work is on a very theoretical and abstract level. He proudly admits this. Nobody would be more excited about others performing experiments than he would be.
thret 12y ago
"Most people who quote Einstein’s declaration that “God does not play dice” seem not to realize that a dice-playing God would be an /improvement/ over the actual situation." (5.1)
- bcombinator 12y ago
  As if there were an actual ''situation''.
  - coldtea 12y ago
    There IS a physical universe, in case you somehow missed that. The quote about god playing dice doesn't imply god exists -- it's actually about the laws of nature (how the universe operates). God's playing dice is just the phrasing it uses to make it more understandable.
raverbashing 12y ago
Already posted and killed yesterday
- krastanov 12y ago
  It is a completely different article by an actual respected researcher in the field.
- phreeza 12y ago
  I posted the medium article yesterday and deleted it myself when I realised it was actually bogus science from reading the comments.
  - gone35 12y ago
    Why delete it though? The discussion that followed[1] alone was worth it, don't you think? Anyway, for those curious about the medium article[2] (and for posterity's sake), see [3]. [1] https://news.ycombinator.com/item?id=8939750 https://news.ycombinator.com/item?id=8939750 [2] It's from their "physics arxiv blog", by the way --so at the very least someone, somewhere in the discipline found it entertaining enough despite its comic flaws! [3] https://medium.com/the-physics-arxiv-blog/the-astounding-link-between-the-p-np-problem-and-the-quantum-nature-of-universe-7ef5eea6fd7a https://medium.com/the-physics-arxiv-blog/the-astounding-lin...
- wfunction 12y ago
  I actually had no idea, sorry.
lisper 12y ago
Here's a hidden gem: "The key point is that seeing a hidden variable’s history would effectively let us simulate non- collapsing measurements." This fact allows one to dismiss all hidden-variables theories (including Bohm's of course) as having no metaphysical relevance. Hidden variables are the invisible pink unicorn of physics. If you can't measure it, it doesn't exist. Deal with it.
- deleted 12y ago
  [deleted]
  - lisper 12y ago
    I don't think you understand the quantum mechanical concept of hidden variablea. They are not at all the same as classical unknowns.
    - deleted 12y ago
      [deleted]
      - marcosdumay 12y ago
        In Quantum Mechanics, hidden variable theories are ones that reduce QM to a probabilistic (or even deterministic) theory that is local and causal.
        lisper 12y ago
        Not necessarily local. In fact, Bell's theorem shows that local hidden variables theories are not possible (to be technically correct, that all local hidden variables theories produce predictions that are at odds with experiment). The reason Aaronson's statement is cool is because it allows us to eliminate ALL hidden variables theories -- local and non-local -- on metaphysical grounds (i.e. by Occam's razor). Yes, you can produce (non-local) hidden-variables theories whose predictions are consistent with experiment. But if you could assign historical values to those variables that would be tantamount to performing collapse-free measurement and that is (almost certainly) not possible.

94 points by wfunction 12y ago

This is classic Scott Aaronson - in fact, he's suggested on more than one occasion that we should adopt 'NP-hard problems are infeasible for the physical universe to solve' as a law of thermodynamics, arguing that the evidence for this is at least as good as other laws and that a disproof of this would be just as revolutionary. Other Aaronson classics include "Who can name the bigger number?" [1], "Shor, I'll do it" (his layman's explanation of Shor's algorithm for finding hidden abelian subgroups) [2], "Is Quantum Mechanics An Island In Theoryspace?" [3], and his blog turned class turned book "Quantum Computing Since Democritus" [4]. But really there's a ton of gold. He has a really neat explanation of the AKS primality testing algorithm [5] and modeled an imaginary easier-to-build (?) less-powerful-but-probably-more-powerful-than-classic-computers computing machine based on the quantum effects of light [6]. In general his blog tends to accumulate a lot of drama and controversy in its comments (because Prof. Aaronson is very opinionated), which he handles very hilariously. It's worth following him over at Shtetl-Optimized [7]. MIT was smart to have given him tenure. [1] http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html [2] http://www.scottaaronson.com/blog/?p=208 http://www.scottaaronson.com/blog/?p=208 [3] http://www.scottaaronson.com/papers/island.pdf http://www.scottaaronson.com/papers/island.pdf [4] http://www.scottaaronson.com/democritus/ http://www.scottaaronson.com/democritus/ [5] http://www.scottaaronson.com/writings/prime.pdf http://www.scottaaronson.com/writings/prime.pdf [6] http://www.scottaaronson.com/papers/optics.pdf http://www.scottaaronson.com/papers/optics.pdf [7] http://www.scottaaronson.com/blog/ http://www.scottaaronson.com/blog/

deleted 12y ago
[deleted]
scottlocklin 12y ago
Aaronson has a gift for popularization, but the fact of the matter is, mathematicians can be astoundingly impractical. Practically speaking, NP hard problems are solved constantly, at least in an approximate sense, by physical reality and computer algorithms; soap bubbles, chemical dynamics, airline scheduling. The exact solution to any problem is uninteresting, just as the exact value of a real number is uninteresting.
- xnull2guest 12y ago
  Scott Aaronson I think himself would agree, as do I. He has some legitimate counterpoints though too on NP-Hard problems being solved. He points out the canonical instance of such problems "folding protein" (chemical dynamics) can not really count, as proteins that misfold (pryons) are in extremely dangerous molecules: evolution has heavily selected to find proteins that it can fold quickly and reliably. He'll also point out that rocks don't find global minimums - that there are in fact a plethora of these examples. He tests soap bubbles and finds many 'easy' instances where it fail. Namely, he's responded to that criticism countless times - once with an actual physical experiment (the paper itself announces). It very likely is interesting to see to what degree other physical processes can approximately compute otherwise hard problems. It's just not fair to pick Aaronson to do it; he himself would be the first to admit that it isn't his area and that you'd want someone like Champagne to do it. In summary, yeah definitely his work is on a very theoretical and abstract level. He proudly admits this. Nobody would be more excited about others performing experiments than he would be.

thret 12y ago

"Most people who quote Einstein’s declaration that “God does not play dice” seem not to realize that a dice-playing God would be an /improvement/ over the actual situation." (5.1)

bcombinator 12y ago
As if there were an actual ''situation''.
- coldtea 12y ago
  There IS a physical universe, in case you somehow missed that. The quote about god playing dice doesn't imply god exists -- it's actually about the laws of nature (how the universe operates). God's playing dice is just the phrasing it uses to make it more understandable.

raverbashing 12y ago

Already posted and killed yesterday

krastanov 12y ago
It is a completely different article by an actual respected researcher in the field.
phreeza 12y ago
I posted the medium article yesterday and deleted it myself when I realised it was actually bogus science from reading the comments.
- gone35 12y ago
  Why delete it though? The discussion that followed[1] alone was worth it, don't you think? Anyway, for those curious about the medium article[2] (and for posterity's sake), see [3]. [1] https://news.ycombinator.com/item?id=8939750 https://news.ycombinator.com/item?id=8939750 [2] It's from their "physics arxiv blog", by the way --so at the very least someone, somewhere in the discipline found it entertaining enough despite its comic flaws! [3] https://medium.com/the-physics-arxiv-blog/the-astounding-link-between-the-p-np-problem-and-the-quantum-nature-of-universe-7ef5eea6fd7a https://medium.com/the-physics-arxiv-blog/the-astounding-lin...
wfunction 12y ago
I actually had no idea, sorry.

lisper 12y ago

Here's a hidden gem: "The key point is that seeing a hidden variable’s history would effectively let us simulate non- collapsing measurements." This fact allows one to dismiss all hidden-variables theories (including Bohm's of course) as having no metaphysical relevance. Hidden variables are the invisible pink unicorn of physics. If you can't measure it, it doesn't exist. Deal with it.

deleted 12y ago
[deleted]
- lisper 12y ago
  I don't think you understand the quantum mechanical concept of hidden variablea. They are not at all the same as classical unknowns.
  - deleted 12y ago
    [deleted]
    - marcosdumay 12y ago
      In Quantum Mechanics, hidden variable theories are ones that reduce QM to a probabilistic (or even deterministic) theory that is local and causal.
      - lisper 12y ago
        Not necessarily local. In fact, Bell's theorem shows that local hidden variables theories are not possible (to be technically correct, that all local hidden variables theories produce predictions that are at odds with experiment). The reason Aaronson's statement is cool is because it allows us to eliminate ALL hidden variables theories -- local and non-local -- on metaphysical grounds (i.e. by Occam's razor). Yes, you can produce (non-local) hidden-variables theories whose predictions are consistent with experiment. But if you could assign historical values to those variables that would be tantamount to performing collapse-free measurement and that is (almost certainly) not possible.