[math-fun] P vs. NP Problem Linked To the Quantum Nature of the Universe
http://science-beta.slashdot.org/story/14/04/04/1610237/p-vs-np-problem-link... <http://beta.slashdot.org/%7ESoulskill>Soulskill (1459) posted 11 hours ago | from the schrodingers-cat-is-both-alive-and-equal-to-NP dept. <http://science-beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: "One of the greatest mysteries in science is why we don't see quantum effects on the macroscopic scale; why Schrodinger's famous cat cannot be both alive and dead at the same time. Now <https://medium.com/the-physics-arxiv-blog/7ef5eea6fd7a>one theorist says the answer is because P is NOT equal to NP. Here's the thinking: The equation that describes the state of any quantum object is called <http://en.wikipedia.org/wiki/Schrodingers_equation>Schrodinger's equation. Physicists have always thought it can be used to describe everything in the universe, even large objects, and perhaps the universe itself. But the new idea is that this requires an additional assumption that an efficient algorithm exists to solve the equation for complex macroscopic systems. But is this true? The <http://arxiv.org/abs/1403.7686>new approach involves showing that the problem of solving Schrodinger's equation is <http://en.wikipedia.org/wiki/Np-hard>NP-hard. So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently. And because all NP-hard problems are mathematically equivalent, this algorithm must also be capable of solving all other NP-hard problems too, such as the traveling salesman problem. In other words, NP-hard problems are equivalent to the class of much easier problems called P. Or P=NP. But here's the thing: computational complexity theorists have good reason to <http://en.wikipedia.org/wiki/P%3Dnp>think that P is not equal to NP (although they haven't yet proven it). If they're right, then macroscopic superpositions cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!" --- co-chair http://ocjug.org/
I glanced at this article, and IMHO it is silly. It sure would be nice if people would evaluate things before the media machine took off... - Cris On Apr 4, 2014, at 9:39 PM, Ray Tayek <rtayek@ca.rr.com> wrote:
http://science-beta.slashdot.org/story/14/04/04/1610237/p-vs-np-problem-link...
<http://beta.slashdot.org/%7ESoulskill>Soulskill (1459) posted 11 hours ago | from the schrodingers-cat-is-both-alive-and-equal-to-NP dept.
<http://science-beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: "One of the greatest mysteries in science is why we don't see quantum effects on the macroscopic scale; why Schrodinger's famous cat cannot be both alive and dead at the same time. Now <https://medium.com/the-physics-arxiv-blog/7ef5eea6fd7a>one theorist says the answer is because P is NOT equal to NP. Here's the thinking: The equation that describes the state of any quantum object is called <http://en.wikipedia.org/wiki/Schrodingers_equation>Schrodinger's equation. Physicists have always thought it can be used to describe everything in the universe, even large objects, and perhaps the universe itself. But the new idea is that this requires an additional assumption that an efficient algorithm exists to solve the equation for complex macroscopic systems. But is this true? The <http://arxiv.org/abs/1403.7686>new approach involves showing that the problem of solving Schrodinger's equation is <http://en.wikipedia.org/wiki/Np-hard>NP-hard. So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently. And because all NP-hard problems are mathematically equivalent, this algorithm must also be capable of solving all other NP-hard problems too, such as the traveling salesman problem. In other words, NP-hard problems are equivalent to the class of much easier problems called P. Or P=NP. But here's the thing: computational complexity theorists have good reason to <http://en.wikipedia.org/wiki/P%3Dnp>think that P is not equal to NP (although they haven't yet proven it). If they're right, then macroscopic superpositions cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!"
--- co-chair http://ocjug.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let me update my response: I have looked more carefully at the paper, and it is totally wrong. Schrodinger's equation is not NP-complete; in all likelihood, it is neither in NP (in the sense the author wants it to be), nor is it NP-hard (because quantum annealing probably doesn't let us solve NP-complete problems, since hard instances have small spectral gaps). The whole thing is incoherent. Cris On Apr 4, 2014, at 9:39 PM, Ray Tayek <rtayek@ca.rr.com> wrote:
http://science-beta.slashdot.org/story/14/04/04/1610237/p-vs-np-problem-link...
<http://beta.slashdot.org/%7ESoulskill>Soulskill (1459) posted 11 hours ago | from the schrodingers-cat-is-both-alive-and-equal-to-NP dept.
<http://science-beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: "One of the greatest mysteries in science is why we don't see quantum effects on the macroscopic scale; why Schrodinger's famous cat cannot be both alive and dead at the same time. Now <https://medium.com/the-physics-arxiv-blog/7ef5eea6fd7a>one theorist says the answer is because P is NOT equal to NP. Here's the thinking: The equation that describes the state of any quantum object is called <http://en.wikipedia.org/wiki/Schrodingers_equation>Schrodinger's equation. Physicists have always thought it can be used to describe everything in the universe, even large objects, and perhaps the universe itself. But the new idea is that this requires an additional assumption that an efficient algorithm exists to solve the equation for complex macroscopic systems. But is this true? The <http://arxiv.org/abs/1403.7686>new approach involves showing that the problem of solving Schrodinger's equation is <http://en.wikipedia.org/wiki/Np-hard>NP-hard. So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently. And because all NP-hard problems are mathematically equivalent, this algorithm must also be capable of solving all other NP-hard problems too, such as the traveling salesman problem. In other words, NP-hard problems are equivalent to the class of much easier problems called P. Or P=NP. But here's the thing: computational complexity theorists have good reason to <http://en.wikipedia.org/wiki/P%3Dnp>think that P is not equal to NP (although they haven't yet proven it). If they're right, then macroscopic superpositions cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!"
--- co-chair http://ocjug.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Not to mention that Schrodinger's equation doesn't describe the real world. At best it's a non-relativistic approximation. On 05-Apr-14 01:54, Cris Moore wrote:
Let me update my response: I have looked more carefully at the paper, and it is totally wrong. Schrodinger's equation is not NP-complete; in all likelihood, it is neither in NP (in the sense the author wants it to be), nor is it NP-hard (because quantum annealing probably doesn't let us solve NP-complete problems, since hard instances have small spectral gaps). The whole thing is incoherent.
Cris
On Apr 4, 2014, at 9:39 PM, Ray Tayek <rtayek@ca.rr.com> wrote:
http://science-beta.slashdot.org/story/14/04/04/1610237/p-vs-np-problem-link...
<http://beta.slashdot.org/%7ESoulskill>Soulskill (1459) posted 11 hours ago | from the schrodingers-cat-is-both-alive-and-equal-to-NP dept.
<http://science-beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: "One of the greatest mysteries in science is why we don't see quantum effects on the macroscopic scale; why Schrodinger's famous cat cannot be both alive and dead at the same time. Now <https://medium.com/the-physics-arxiv-blog/7ef5eea6fd7a>one theorist says the answer is because P is NOT equal to NP. Here's the thinking: The equation that describes the state of any quantum object is called <http://en.wikipedia.org/wiki/Schrodingers_equation>Schrodinger's equation. Physicists have always thought it can be used to describe everything in the universe, even large objects, and perhaps the universe itself. But the new idea is that this requires an additional assumption that an efficient algorithm exists to solve the equation for complex macroscopic systems. But is this true? The <http://arxiv.org/abs/1403.7686>new approach involves showing that the problem of solving Schrodinger's equation is <http://en.wikipedia.org/wiki/Np-hard>NP-hard. So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently. And because all NP-hard problems are mathematically equivalent, this algorithm must also be capable of solving all other NP-hard problems too, such as the traveling salesman problem. In other words, NP-hard problems are equivalent to the class of much easier problems called P. Or P=NP. But here's the thing: computational complexity theorists have good reason to <http://en.wikipedia.org/wiki/P%3Dnp>think that P is not equal to NP (although they haven't yet proven it). If they're right, then macroscopic superpositions cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!"
--- co-chair http://ocjug.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Cris Moore -
Mike Speciner -
Ray Tayek