Forgot your password?
typodupeerror
Math Science

P vs. NP Problem Linked To the Quantum Nature of the Universe 199

Posted by Soulskill
from the schrodingers-cat-is-both-alive-and-equal-to-NP dept.
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!"
This discussion has been archived. No new comments can be posted.

P vs. NP Problem Linked To the Quantum Nature of the Universe

Comments Filter:
  • Say what? (Score:5, Insightful)

    by mbone (558574) on Friday April 04, 2014 @12:30PM (#46661869)

    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.

  • by david_thornley (598059) on Friday April 04, 2014 @12:32PM (#46661887)

    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)

    by Knee Patch (2647703) on Friday April 04, 2014 @12:34PM (#46661923)
    Agreed. I got lost right around here in the summary:

    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)

    by colinrichardday (768814) <colin.day.6@hotmail.com> on Friday April 04, 2014 @12:38PM (#46661973)

    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)

    by quax (19371) on Friday April 04, 2014 @12:54PM (#46662155)

    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.

  • by Tablizer (95088) on Friday April 04, 2014 @01:00PM (#46662223) Homepage Journal

    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.)

  • by draconx (1643235) on Friday April 04, 2014 @01:09PM (#46662305) Homepage
    NP-hard problems are absolutely not all equivalent. NP-hard is a class of decision problems which literally means any problem which is "at least as difficult" as problems which are in NP. To posit that all NP-hard problems are equivalent would imply that there's some sort of upper bound on problem "difficulty". This is absurd for a number of reasons. First of all, this claim implies that NP is equal to EXPSPACE (EXPSPACE-complete problems are NP-hard after all) which is not true (there is known to be an inequality between these two sets). But moreover NP-hard problems are not necessarily even computable -- the halting problem is NP-hard! To claim this is equivalent to 3-SAT is just ridiculous. tl;dr: The Venn diagrams in the article shows the relationship between these complexity classes correctly but the writer seems very confused about them.
  • by Anonymous Coward on Friday April 04, 2014 @01:23PM (#46662505)
    Much like the summary.
  • by Anonymous Coward on Friday April 04, 2014 @01:34PM (#46662611)

    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)

    by rgbatduke (1231380) <rgb@nOSpAM.phy.duke.edu> on Friday April 04, 2014 @02:19PM (#46663057) Homepage

    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

  • by skywire (469351) on Friday April 04, 2014 @02:32PM (#46663209)

    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.

Nothing is more admirable than the fortitude with which millionaires tolerate the disadvantages of their wealth. -- Nero Wolfe

Working...