P vs. NP Problem Linked To the Quantum Nature of the Universe 199
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 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 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 new approach involves showing that the problem of solving Schrodinger's equation is 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 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!"
Say what? (Score:5, Insightful)
I have not had time to read the article, but the summary is either incoherent or wrong.
Here is an analog to illustrate why :
The basic equations for fluid dynamics are the Navier-Stokes equation. 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?
In the case of the Navier-Stokes equation, almost certainly not. In fact, it is generally not even clear if solutions even exist, or if they are non-singular.
If this is right, then complex fluid motions cannot exist, which explains why we do not (and cannot) observe them in the real world. Voila!"
So, I guess we can cancel this years hurricane season.
In other words, there are many things in nature that are computationally hard, and yet happen any way. Using computational hardness as a reason why a physical theory cannot be right does not, to put it mildly, agree with past experience.
NP vs. P doesn't exist in the real Universe (Score:5, Insightful)
The whole P vs. NP thing is in computation involving discrete states. The relevant proofs are of computers and Turing machines. There's nothing saying some sort of natural process can't do something NP-hard fast, as long as it doesn't do it in some way we'd call computation.
The mistake is in "So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently." If the superpositions exist, there must be a way to solve that NP-hard problem, not necessarily an algorithm.
To quote Wikipedia [wikipedia.org], "An algorithm is an effective method expressed as a finite list[1] of well-defined instructions[2] for calculating a function.". Any process that is not simply a collection of well-defined instructions can calculate whatever it likes, as far as Computer Science goes.
Re:Say what? (Score:5, Insightful)
So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently.
Maybe the paper has a really great argument to support this assertion, but it doesn't seem obvious to me.
Re:Say what? (Score:4, Insightful)
Also, nature doesn't have to solve the Napier-Stokes equation. Unless you take the resulting arrangement of stuff as a solution.
Cringeworthy (Score:5, Insightful)
From the summary:
Physicists have always thought [Schrodinger's equation] can be used to describe everything in the universe
What physicists would that be?
The Schrodinger's equation is none-relativistic and doesn't ever capture QED.
Only quantum information dilettantes who never graduated beyond the unitary world of simple quantum systems could believe such a nonsense.
Re:Computable? Simulatable? (Score:5, Insightful)
My impression is that it's saying that quantum effects perhaps can in theory be used to explain macro-physics, but it's too difficult for humanity to run the models to compute the macro affects using quantum models such that we are stuck with separate models (approximations) for the macro side versus the micro-side.
In other words, a near-perfect simulation of quantum affects may properly mirror macro-effects in an emergent-behavior kind of way, but doing such is not practical using existing computer technology.
It's roughly comparable to the human brain: we have plenty of nice little models of neurons and small neural nets, but we don't have the computational power to see if it matches human behavior on a bigger scale. (It's probably more than just horse-power; many of the organizational details are still murky, but just go with me on this as a rough example.) Thus, we are stuck with "psychology" for the large scale instead of modelling human behavior at the neuron level.
I don't think they are saying that the universe itself can't "run" the "computations", but that part is not clear. We don't know that the universe's OS is time-dependent or even what the universe's OS is (although its predicted birth and death pattern resembles Windows: designed to run so many years until enough cruft builds up over time that it slows to a crawl such that it becomes indistinguishable from no OS, and then you have trash the whole thing, keep a few pet files, buy version Windows N+1 and install from scratch. Elvis and Michael Jackson are two of the "pet files" kept from Universe N-1, I bet, and they'll be put back into N+1.)
Re:Are all NP-hard Problems equivalent? (Score:4, Insightful)
Re:I prefer the chewbacca argument (Score:2, Insightful)
Re:All hail the multi-verse. (Score:4, Insightful)
Actually, no. Infinite number of universes does not mean that there is a universe for anything you can imagine. Just like 6 is not between 2 and 3, despite of infinite number of numbers being there.
Re:Say what? (Score:5, Insightful)
Nature doesn't solve any equations at all. Equations describe what nature does. Electrons do not contain calculators.
If you like, you can consider the Universe itself to be a really big calculator, but if so it isn't computing something else -- the computation is the self-consistent dynamical evolution of the Universe itself.
So of all of the arguments against Schrodinger's Cat (which requires a non-existent non-relativistic local partitioning in the first place) this one is the nuttiest IMO. Why not simply work through the Nakajima-Zwanzig repartitioning of a "unversal" density matrix into a generalized master equation (ideally retaining relativistic non-locality in time) and acknowledge that since we cannot formally adiabatically disconnect the interior of the box from the rest of the Universe, the state of the interior is always coupled to the exterior state in such a way that the cat is dead or not dead but not both?
rgb
Re:Computable? Simulatable? (Score:5, Insightful)
whether the world really exists or could be a simulation/fantasy/etc
Anyone who thinks there is a distinction between the two has not thought enough.