Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

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

Soulskill posted about 6 months ago | from the schrodingers-cat-is-both-alive-and-equal-to-NP dept.

Math 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!"

cancel ×

199 comments

Sorry! There are no comments related to the filter you selected.

I prefer the chewbacca argument (1)

Anonymous Coward | about 6 months ago | (#46661821)

Schrodinger's cat is definitely dead. Chewbacca ate it.

Re:I prefer the chewbacca argument (2, Funny)

Anonymous Coward | about 6 months ago | (#46662449)

That does not make sense.

Re:I prefer the chewbacca argument (2, Insightful)

Anonymous Coward | about 6 months ago | (#46662505)

Much like the summary.

!P is not NP and NP-Hard is not NP-Complete (1)

mr_mischief (456295) | about 6 months ago | (#46661833)

See the subject.

NP-Hard is not the same thing as NP-Complete the last time I checked. Neither is NP yet known to be non-P nor P. That's why it's NP (nondeterministic polynomial). P would never be equal to NP. NP may be a subset of P. There are problems that are both NP-hard and NP-complete, but not all NP-hard problems are NP-complete. That means that solving one NP-hard problem is not necessarily equivalent to solving the NP-complete problem set.

Re:!P is not NP and NP-Hard is not NP-Complete (4, Informative)

allo (1728082) | about 6 months ago | (#46661899)

no, P will always be a (real) subset of NP.

You can solve all problems in P with a non-deterministic turing machine. You have problems in P, which are not NP-hard.
[ ]

Re:!P is not NP and NP-Hard is not NP-Complete (1)

lgw (121541) | about 6 months ago | (#46662275)

You can solve all problems in P and NP both, eventually. There's no need for the universe to be efficient to simulate. TFA boggles me: what does the efficiency of the computation matter?

Re:!P is not NP and NP-Hard is not NP-Complete (1)

cruff (171569) | about 6 months ago | (#46662341)

TFA boggles me: what does the efficiency of the computation matter?

It seems to me to equate to define the limit where collapse of the wave function is guaranteed?

Re:!P is not NP and NP-Hard is not NP-Complete (1)

geekmux (1040042) | about 6 months ago | (#46662617)

You have problems in P, which are not NP-hard. [ ]

Well, as long as you don't have problems in P-hard.

If you do discover them, I'd recommend a urologist, not a mathematician.

Re:!P is not NP and NP-Hard is not NP-Complete (1)

Anonymous Coward | about 6 months ago | (#46662343)

No, no, no. Either P is a subset of NP, or P=NP. NP cannot be a subset of P.

http://en.wikipedia.org/wiki/File:P_np_np-complete_np-hard.svg

Re:!P is not NP and NP-Hard is not NP-Complete (1)

LifesABeach (234436) | about 6 months ago | (#46662519)

Just a thought, but Soulskill is stating that the solution is unknown to Soulskill. Carry on.

Computable? Simulatable? (4, Interesting)

Remus Shepherd (32833) | about 6 months ago | (#46661861)

Hmn. This sounds as if they are trying to prove that the essential nature of quantum mechanics is not computable. I wonder, if they framed this research another way, if it could solve the question of whether or not the universe is a simulation. (I suspect not, it might just indicate that classical and quantum objects are simulated in different ways.)

Re:Computable? Simulatable? (5, Insightful)

Tablizer (95088) | about 6 months ago | (#46662223)

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:Computable? Simulatable? (1)

Camel Pilot (78781) | about 6 months ago | (#46662523)

I don't think they are saying that the universe itself can't "run" the "computations"

Just more proof that reality is a simulation... the programmer, due to limitations of cpu, had to resort optimizations at the microscale.

Re:Computable? Simulatable? (1)

postmortem (906676) | about 6 months ago | (#46662811)

Maybe Heaven is just a better simulation...

Re:Computable? Simulatable? (2)

Tablizer (95088) | about 6 months ago | (#46663051)

Maybe Heaven is just a better simulation...

Heaven is Emacs and hell is MS-Office with DLL's mixed from different versions due to the screwy installer......oh wait, that's here-and-now.

Re:Computable? Simulatable? (2)

TheCarp (96830) | about 6 months ago | (#46662613)

I remember one of the smart but more humanities oriented friends of mine tried to engage the AP Physics teacher in a debate about whether the world really exists or could be a simulation/fantasy/etc. At the first posing of the question, the teacher immediately turned and flung himself bodily against the wall and exclaimed that it seemed pretty real to him.

I think there is an insight there that is lost often. If the world is a simulation, then how would we ever know as we have nothing to compare it to? Sure we can suspect, we can show that some quirks of quantities in this universe can be explained by the universe being a simulation of some sort..... but, those quircks would always be the only reference we have to compare against.

> I don't think they are saying that the universe itself can't "run" the "computations", but
> that part is not clear.

I thought they were clear when they said "He says there is an implicit assumption when physicists say that SchrÃdingerâ(TM)s equation can describe macroscopic systems. This assumption is that the equations can be solved in a reasonable amount of time to produce an answer."

So, if you can't solve the equation for an answer, you can't make a prediction. Take the system of the cat in the box, it is commonly said that the cat should be in a superposition of states but... that isn't based on someone solving the wave function....that is a guess based on understanding the general form of the wave function. Nobody can actually solve the wave function for a real system to the point that it completely represents an entire cat in a superposition.

Since they can't do that, the prediction that the cat should be in a superposition is not a valid hypothesis; it is more like a guess at what the testable result would be if you could compute it.

Re:Computable? Simulatable? (0)

Anonymous Coward | about 6 months ago | (#46662861)

Very easy. Make the universe throw a BUS ERROR. Then you know.

Re:Computable? Simulatable? (0)

Anonymous Coward | about 6 months ago | (#46662879)

Thinking about it, maybe Black Holes are indeed the same as a bus error.

Re:Computable? Simulatable? (1)

TheCarp (96830) | about 6 months ago | (#46662993)

I wonder how many universes end when their inhabitants cause a fault in the code and their designer fails his simulation class.

Re:Computable? Simulatable? (1)

michelcolman (1208008) | about 6 months ago | (#46663113)

They'll just restart it from a recent backup and we'll never even know it happened. If you were to start your life again yesterday, without remembering anything from yesterday or today, the whole world including your mind restored exactly to the state it was in yesterday, then time would appear uninterrupted. So if you keep trying to generate bus errors which keep getting fixed with a reboot/restore, it will appear that none of the experiments worked and you might conclude that the universe is not a simulation. In fact, there's no way these bus error experiments would ever result in anyone concluding it is a simulation.

Re:Computable? Simulatable? (1)

Tablizer (95088) | about 6 months ago | (#46663159)

This assumption is that the equations can be solved in a reasonable amount of time to produce an answer

"Solved" (computed) by humans or by the "mechanisms" of the universe?

So, if you can't solve the equation for an answer, you can't make a prediction.

We don't necessarily have to make real-time predictions to test the model. We can "film" the experiment now and compare it against a simulation that may take 100 years to run, for example.

Or are you suggesting that the very act of knowing or not knowing the result of the computation affects what we observe? In other words, are they talking about the quantum meme of "observing changes what's being observed"? (AKA, "inadvertent observer interference".)

Re:Computable? Simulatable? (1)

ultranova (717540) | about 6 months ago | (#46662941)

We don't know that the universe's OS is time-dependent

Who's time? Every simulation runs in real-time as far as the simulated agents are concerned. And time is a feature of the universe; if universe is a simulation, why assume the "external" world has time?

All hail the multi-verse. (1)

goombah99 (560566) | about 6 months ago | (#46662465)

I wonder, if they framed this research another way, if it could solve the question of whether or not the universe is a simulation.

Enough with your silly dichotomies! it's both. In multi-verse theory, there must be some realities in which our universe is a simulation, and ones in which it is not a simulation.

Re:All hail the multi-verse. (0)

Anonymous Coward | about 6 months ago | (#46662511)

M I N D ... B L O W N. This is what I get for gurgling a bowl before breakfast and then reading slashdot. For a moment I was in both realities.

Re:All hail the multi-verse. (4, Insightful)

Anonymous Coward | about 6 months ago | (#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:All hail the multi-verse. (3, Funny)

goombah99 (560566) | about 6 months ago | (#46662951)

That's just what the Flying Spaghetti Monster wants you to think.

Re:All hail the multi-verse. (1)

njnnja (2833511) | about 6 months ago | (#46663129)

Yeah but in one of the universes there was a mathematician named 6ul6r and so 6 *is* between 2 and 3

Re:All hail the multi-verse. (1)

The Grim Reefer (1162755) | about 6 months ago | (#46663167)

Just like 6 is not between 2 and 3, despite of infinite number of numbers being there.

Yes it is (depending on the context):

263

2... 6... 30

6.2, 6.3

2,6,3,7...

Re:All hail the multi-verse. (1)

narcc (412956) | about 6 months ago | (#46663015)

Wow, no. Where did you come up with that bit of insanity?

Please tell me you're joking.

Are all NP-hard Problems equivalent? (1)

allo (1728082) | about 6 months ago | (#46661865)

For most (all?) they are proven as np-hard, because they can be used to solve a NP-hard problem with a transformation, which lies in P. But is there any proof, that you can transform any NP-hard problem into any other? If you think of a graph of np-hard problems (i guess most go back via a few hops to 3SAT?), then there may be different connected components, or is there a proof, why the graph is connected?

Re:Are all NP-hard Problems equivalent? (1)

allo (1728082) | about 6 months ago | (#46661919)

(all?) = (all known?)

Re:Are all NP-hard Problems equivalent? (2)

david_thornley (598059) | about 6 months ago | (#46661999)

To simplify things a bit, the basic proof that the SAT problem is NP-complete involves expressing a Turing machine in terms of SAT. Therefore, any problem that can be run on a Turing machine is no harder than SAT, because we could always transform such a problem to SAT and solve that.

There are other problems that SAT can be expressed as, and they're also NP-complete. Therefore, within a polynomial factor, all NP-complete problems are equally hard.

Re:Are all NP-hard Problems equivalent? (2)

allo (1728082) | about 6 months ago | (#46662121)

So you can use SAT to implement a turing machine, you can use the TSP to implement SAT. But if you have a new NP-hard problem, which can be simulated by a non-deterministic TM, this does not tell you, that the problem can simulate a a TM or SAT? Or is it an requirement for a np-hard problem not only to run on a TM, but to implement one, as SAT does?

Re:Are all NP-hard Problems equivalent? (1)

timeOday (582209) | about 6 months ago | (#46662883)

Keep in mind words like "no harder" are pretty misleading to a non-theorist, since the known classes of computational complexity are so loose in the first place. IIRC the transformation need only be polynomial, right? So, two problems could be of "equal" difficulty when one is literally a zillion times harder than the other (since a zillion is only a constant), or even n to the power of a zillion (since that's "just" a polynomial). Computational theory is practically blind to constants, but you know what, there are a lot of particles in the universe, they could conceivably brute-force some awfully big problems.

Re:Are all NP-hard Problems equivalent? (2)

marcosdumay (620877) | about 6 months ago | (#46662209)

A solution to a NP-hard problem can be used to solve any NP problem, but a NP-hard may, or may not be an NP problem. What means that no, not all NP-hard problems are equivalent (and that's for sure).

The set where all are equivalent is named "NP-complete". Those are the NP-hard problem that are also NP.

Re:Are all NP-hard Problems equivalent? (3, Insightful)

draconx (1643235) | about 6 months ago | (#46662305)

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.

Re:Are all NP-hard Problems equivalent? (1)

Nemyst (1383049) | about 6 months ago | (#46662835)

That's a bit pedantic. When saying "NP-hard problem", you usually mean it as an upper bound as opposed to a lower bound. Nobody would describe an EXPSPACE problem as "NP-hard" because that's completely besides the point.

Re:Are all NP-hard Problems equivalent? (2)

ImprovOmega (744717) | about 6 months ago | (#46662589)

All NP-Complete problems reduce to each other. If memory serves, factoring is not NP-complete, but any NP-complete problem can reduce to factoring, just not the other way around. NP-hard is actually a harder set than NP-complete. Any NP-hard solution could be used to solve and NP-complete problem, but not the other way around.

N=1 (1)

Anonymous Coward | about 6 months ago | (#46661867)

P is equal to NP only if N=1. Voila!

Re:N=1 (2, Informative)

colinrichardday (768814) | about 6 months ago | (#46661947)

Or P=0.

Say what? (5, Insightful)

mbone (558574) | about 6 months ago | (#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.

Re:Say what? (5, Insightful)

Knee Patch (2647703) | about 6 months ago | (#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? (5, Interesting)

Anonymous Coward | about 6 months ago | (#46661933)

"Nature is not embarrassed by difficulties of analysis." -- Augustin Fresnel

Re:Say what? (1)

careysub (976506) | about 6 months ago | (#46662929)

Excellent quote AC, thanks!

Re:Say what? (3, Insightful)

colinrichardday (768814) | about 6 months ago | (#46661973)

Also, nature doesn't have to solve the Napier-Stokes equation. Unless you take the resulting arrangement of stuff as a solution.

Re:Say what? (1)

Anonymous Coward | about 6 months ago | (#46662381)

Nature also doesn't have to solve the Navier-Stokes equation because real fluids consist of particles, not a continuum, and therefore the behavior of real fluids is only approximated by the Navier-Stokes equations.

Re:Say what? (1)

GodInHell (258915) | about 6 months ago | (#46662393)

Nature is a big fan of brute force solutions to complex equations - it just does shit and reports the result.

Re:Say what? (0)

Anonymous Coward | about 6 months ago | (#46662501)

If "nature" is really just a computer running a simulation that we live inside, then it certainly does have to solve the equations for fluid dynamics (and quantum mechanics, and more). Sucks for us, running our own simulations, but I don't see why "the problem is difficult/currently infeasable" means "nobody will solve it."

Re:Say what? (1)

Rich0 (548339) | about 6 months ago | (#46662503)

Also, nature doesn't have to solve the Napier-Stokes equation. Unless you take the resulting arrangement of stuff as a solution.

I think that was exactly the argument being employed - you can model a hurricane simply by building another Earth and letting it run. Does that mean that modeling hurricanes isn't actually NP?

I'm not knowledgeable enough about the technical definition of P vs NP to say whether NP problems can never be calculated by a quantum computer (which ultimately is what the whole of the universe is).

Actually, the real problem with modelling hurricanes is that the system is chaotic - unless you know the position and velocity of every subatomic particle (including photons/etc) within a few light-days of the storm you can't run a simulation that truly takes everything into account. All it takes is one cosmic ray triggering a bolt of lightning somewhere to make your simulation start to deviate. So, even if you could create another Earth to run the simulation on, you could never initialize it properly. I'm not sure if that really has any bearing on the NP-ness of the problem, though.

Re:Say what? (4, Insightful)

rgbatduke (1231380) | about 6 months ago | (#46663057)

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:Say what? (2)

xandos (1350159) | about 6 months ago | (#46662301)

Very much agreed. Nature is not restricted by what we can compute.

It makes me wonder though. It makes sense that we cannot restrict physics to behave according to our computational prowess, but we if we turn this logic onto itself? Is the line of reasoning explored in the article inconsistent with Goedels theorem? Or should I hurry and go back to a computational complexity course?

Re:Say what? (0)

Anonymous Coward | about 6 months ago | (#46662309)

Nature isn't solving navier-stokes. It's running a finite-element particle-based simulation!

Re:Say what? (1)

kruach aum (1934852) | about 6 months ago | (#46662431)

I was going to post exactly this. The summary provides no reason to assume that the extra assumption is warranted or even logical.

Re:Say what? (1)

Rich0 (548339) | about 6 months ago | (#46662705)

The basic equations for fluid dynamics are the Navier-Stokes equation.

So, I fully grok your argument, but I am wondering about one thing.

Is the Navier-Stokes equation REALLY the basic equation for fluid dynamics? Or is it just a really good approximation?

That is the difference between classical physics and quantum mechanics. The former only generally works on macroscopic objects that are governed by the statistical average behaviors of the constituent particles. If I hit a baseball so hard, it flies so far, and I don't need to know how many C-12 vs C-13 vs C-14 atoms are inside of it to make the math work.

The Schrodinger equation does actually purport to describe the behavior of quantum systems at a level where they are indivisible.

So, in that sense a hurricane is governed more by the Schrodinger equation than Navier-Stokes, even if the latter is more useful in practice (precisely because you can solve it without modeling it to the subatomic level).

I think you still raised a great argument. It just might not be mathematically rigorous in the sense that proving/disproving the one analogy has a certain bearing on the other.

Re:Say what? (2)

TheCarp (96830) | about 6 months ago | (#46662741)

I think you have it backwards and a bad example. They are looking for a predicted result and not seeing it; this strikes me at an attempt at asking if the prediction itself could be wrong.

When it comes to a quantum superposition of states, you need look no further than papers on the Bell Inequality to see a well defined situation with well defined predicted outcomes. Thouse outcomes clearly come down on the side of the predicted superpositions.

Then look at the cat problem. What does it even mean for the entire cat to be in a superposition of living and dead? Is it really a prediction of the wave equation or is it ignoring the realities of underlying complexity, the same complexity that makes the wave equation impossible to calculate.

Without being able to say with certainty what the prediciton is, do you actually even have a hypothesis?

brain will explode now. (5, Funny)

schlachter (862210) | about 6 months ago | (#46661873)

BOOM.

Re:brain will explode now. (0)

Anonymous Coward | about 6 months ago | (#46661881)

Ditto

Re:brain will explode now. (0)

Anonymous Coward | about 6 months ago | (#46662383)

I'm still trying to figure out why that encyclopedia salesman keeps dropping by with a box full of half-dead cat.

NP vs. P doesn't exist in the real Universe (4, Insightful)

david_thornley (598059) | about 6 months ago | (#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:NP vs. P doesn't exist in the real Universe (1)

mbone (558574) | about 6 months ago | (#46662225)

And that is basically my response to the AI proponents who say "a computer can calculate anything a brain can think."

Re:NP vs. P doesn't exist in the real Universe (1)

Charliemopps (1157495) | about 6 months ago | (#46662841)

A Brain IS a computer. So they're right. Just because in the past 50years or so we haven't figured out how to build one as good as nature did in several billion doesn't mean it's not going to happen eventually.

Re:NP vs. P doesn't exist in the real Universe (0)

Anonymous Coward | about 6 months ago | (#46663023)

In what sense are they right? My artificial computer can calculate complex mathematical calculations much more efficiently than you can.

But it isn't "thinking". Which leaves us with the problem you started with. You don't know what "what you are thinking" is made of. You're assuming that it in some way relates the the output of a set of distributed calculations that you could encode in an equivalent physical manner without manifesting it in your brain.

And you & I probably would prefer that it does, but it's not evidence.

Re:NP vs. P doesn't exist in the real Universe (1)

marcosdumay (620877) | about 6 months ago | (#46662249)

A way to solve a problem is an algorithm for some kind of computer (to use the example of a previous post, a hurricane does compute the Navier-Stokes equations for a set of parameters).

The article gets crazy only when it requires that the algorithm be quick and efficient.

Re:NP vs. P doesn't exist in the real Universe (1)

lgw (121541) | about 6 months ago | (#46662349)

Well, if the universe can do it then a simulation must exists that can do it, it's just a question of efficiency. However, that doesn't change anything in your argument. We don't know how the universe actually works, we merely have predictive models. Predictive models are great and all, but they aren't unique: for any set of data, there are an infinity of models that are consistent wit that data - and it's hard to say much about all the models you're not using.

Re:NP vs. P doesn't exist in the real Universe (2)

mbone (558574) | about 6 months ago | (#46662561)

Well, if the universe can do it then a simulation must exists that can do it, it's just a question of efficiency.

Not true for chaotic systems, which are incredibly common in nature. The coffee and cream in your cup can be simulated, but not computed, and the situation is much, much, worse for (say) a Hurricane, or the Great Red Spot, or a Galaxy.

I do agree with you about the limitations of predictive models...

Re:NP vs. P doesn't exist in the real Universe (2)

lgw (121541) | about 6 months ago | (#46662627)

Sure it can be computed. If you include the non-determinism of it all, you won't get the same answer as the universe does, but you'll get a perfectly good answer. Without the non-determinism you'll get the exact answer. You might not get it within the lifetime of the universe, but that's a mere efficiency concern.

Re:NP vs. P doesn't exist in the real Universe (0)

Anonymous Coward | about 6 months ago | (#46663061)

You're suggesting that the Physical Church-Turing thesis [wikipedia.org] may be incorrect. I'd suggest that if this is the case, then the right fix is to come up with a better model of what computation means, not to suggest that that physical process is not a computation.

Why would efficency matter? (2)

firewrought (36952) | about 6 months ago | (#46661917)

The distinction that P algorithms are "efficient" and NP algorithms are "inefficient" is merely a convention of complexity theorists. You could easily draw the dividing line further in or out [mit.edu] depending on your purposes. That makes me wonder what constitutes their assumption that this particular P/NP type "efficency" is necessary for a macroscopic Schrodinger algorithm.

Re:Why would efficency matter? (1)

allo (1728082) | about 6 months ago | (#46662043)

The idea is, how they scale. If you think of a finite set of possible inputs, everything is O(1).

Re:Why would efficency matter? (1)

marcosdumay (620877) | about 6 months ago | (#46662257)

On the real world, all computers operate on a finite set of possible inputs.

Possible impact to information theory. (0)

Anonymous Coward | about 6 months ago | (#46661949)

So, the axioms of information theory (and to a lesser extent, math in general) aren't necessarily true, but based on the actual nature of our universe...Mind. Blown.

It could well be, then, that the nature of a given universe (including any possible parallel realities to it) are inherent values of the universe itself and not any underlying structure, if there even is one. A's universe could allow inter-universe travel and co-exist with others, but one of those universes (B's) doesn't allow travel to others at all, nor recognize that it exists.

Schrodinger's Salesforce, or Denny's (5, Funny)

Tablizer (95088) | about 6 months ago | (#46661967)

I'm trying to work this into an everyday analogy of a traveling half-dead-cat salesman, but am getting stuck.

Re:Schrodinger's Salesforce, or Denny's (2)

BronsCon (927697) | about 6 months ago | (#46662135)

A traveling cat salesman starts each day by boxing and shrink-wrapping the cats he hopes to sell that day and ends each day by unboxing his unsold inventory and disposing of any that did not survive.

Use that as a starting point.

Re:Schrodinger's Salesforce, or Denny's (1)

Tablizer (95088) | about 6 months ago | (#46662339)

Does the wave function collapse into reality as soon as a restaurant patron bites into it?

Re:Schrodinger's Salesforce, or Denny's (2)

BronsCon (927697) | about 6 months ago | (#46662415)

Only in Chinatown.

Re:Schrodinger's Salesforce, or Denny's (0)

Anonymous Coward | about 6 months ago | (#46663009)

Have you tried integrating a car analogy. For example maybe one traveling half dead sales cat (cat1) is traveling north along a freeway at seventy miles an hour while another (cat2) traveling half dead sales cat is traveling south along the center of the same freeway at three miles an hour, now obviously if there is an observer of cat 2, the cat will clearly be observed to be either dead or alive however what happens when cat 2 observes cat 1 as dead at the wheel - well we clearly no longer have an observer of cat 2!

How big are we calling 'Macroscopic'? (2)

Bonker (243350) | about 6 months ago | (#46661971)

My understanding is that we have some pretty good examples of 'larger than just a few elementary particles' superposition and observer effects that have been demonstrated.

For example, birds' touted ability to navigate by way of feeling the Earth's magnetic field is apparently enhanced by the observer effect.

http://www.wired.com/2009/06/b... [wired.com]

Now... cellular level effects are still pretty small, but it's an example of a living organism we can hold in our hands (and pet, if you're a bird person.) learning to use quantum effects in its everyday life.

For an example of superposition in living organisms, one needs to look no further than our abundant flora, where superposition apparently increases the efficiency of photosynthesis, without which our current biosphere would pretty much collapse and we'd all die.

http://mappingignorance.org/20... [mappingignorance.org]

So, I think we're looking at a bell-curve like thing here. The bigger the 'observability' of a phenomenon, the less likely we are to experience it in our lifetimes. My guess is that huge, say, planetary-scale, examples of superposition are quite possible... just so very unlikely that one hasn't happened observably in human history (and probably the history of the universe.)

Premise is wrong (0)

Anonymous Coward | about 6 months ago | (#46662027)

Macroscopic outcome of quantum effects can be observed every day. Every chemical reaction and every electronic operation are macroscopic outcomes of the Schrodinger equation.

Re:Premise is wrong (0)

Anonymous Coward | about 6 months ago | (#46662307)

Yes, but they do not manifest the quantum nature, they do not show all the strange stuff like entanglement or superposition of weird states.

Cringeworthy (4, Insightful)

quax (19371) | about 6 months ago | (#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.

Uhm.... (0)

Anonymous Coward | about 6 months ago | (#46662245)

Isn't the radiation monitor an observer?

I dont think there is anything saying (0)

Anonymous Coward | about 6 months ago | (#46662273)

A natural process cant compute.

Terrible (2)

sexconker (1179573) | about 6 months ago | (#46662287)

"Physicists have always thought it can be used to describe everything in the universe, even large objects, and perhaps the universe itself."
Nope. Nope nope nope.

"So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently."
What? Why would you claim that?

Stopped reading TFS there. It's clearly useless wankery.

Calling BS (0)

Anonymous Coward | about 6 months ago | (#46662289)

It could just as easily mean that quantum computers will be able to solve NP-Hard problems efficiently.

NP does not mean not computable (0)

Anonymous Coward | about 6 months ago | (#46662359)

The paper proving that solving the Schroedinger equation is NP-hard (or NP-complete for the associated decision problem of saying "is there a solution within this solution space subset?", which brings you to the functional problem with binary search) sounds interesting, but the physical conclusions are dubious.
First of all, NP does not mean not computable, because non deterministic Turing machines are not more powerful than deterministic TMs, they just take less time. Which is arguably not very important, when time itself is part of the solution space...
Second, it is yet to be determined that the universe is deterministic. If any, the random behavior of quantum mechanics would be suggest that some non-determinism exists, and when that is accepted, you obtain a system that is capable of solving any kind of (polinomially veriable) equation in polinomial time.
Third, this takes constants out of the way. It might be that simulating a bigger universe takes exponentially more time, but for this universe there is enough time to determine the next state before that occurs.

On a classical computer... (1)

Paxinum (1204260) | about 6 months ago | (#46662369)

Yes, it is hard to solve TSP on a classical computer, but NP-complete problems can be solved efficiently on a quatum computer...

This paper is garbage (0)

Anonymous Coward | about 6 months ago | (#46662413)

So to begin with, the paper starts with what essentially amounts to an incorrect proof that NP = BQP (BQP being the natural class of algorithms that could be run efficiently on a quantum computer). On the one hand, he claims that a solution to the Schrodinger equation can be efficiently verified by a classical computer (it cannot (at least in the way he says) because it lives in a vector space of exponential size) to show that BQP is in NP (it is not believed to be). Then he uses the adiabatic model of quantum computation to claim that BQP is in NP. Unfortunately, the adiabatic model is an approximation, and the author of the paper doesn't show that the approximation actually works in this case without running your quantum state for exponential time. And really BQP is not believed to contain NP either.

In any case, after this the paper trots out the old argument that large scale entanglement cannot exist for complexity reasons. Fine. Let's assume that BQP is not P (i.e. that quantum mechanics can do things that are hard to simulate on a classical computer). Then in order for this argument to work at all you need to assume that the universe can be efficiently simulated on a classical computer. Which... is unproven.

At very least this argument makes an empirical prediction: That large scale quantum computers are impossible. Thus, once someone actually figures out how to build a quantum computer we can laugh at this guy.

Arm waving word plays don't equal proof (0)

Anonymous Coward | about 6 months ago | (#46662481)

Why do you have to have a fast efficient algorthm for solving NP Hard?

  Maybe there are an infinite number of super monkey's, each operating their own Beowulf cluster that started solving various incarnations of the Schroedinger equation, starting at the big bang. As each computation is completed something else pop's into existance, possibly new super monkeys. We have therefore proven that the universe is expanding ... maybe.

Those aren't stars out there, they're just the cooling arrays for the previously mentioned Beowulf clusters.

The method doesn't have to be fast and efficient, just started soon enough, run long enough and be "fast enough".

Regarding arxiv (0)

Anonymous Coward | about 6 months ago | (#46662549)

People should realise by now that everything's that's posted to arxiv should be taken with a grain of salt at least until it's past the refereeing stage(s). In the case of questions related to (self-proclaimed) advances or insights related to the P versus NP question, a whole salt mine is probably more appropriate.

Superpositions do not exist. (2, Interesting)

140Mandak262Jamuna (970587) | about 6 months ago | (#46662569)

So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently.

Super position holds only for linear systems. All this analysis proves is, nature is not linear. That is all. It does not prove quantum mechanics comes from NP hard nature of some equation or another.

Enterprise quote (1)

WaffleMonster (969671) | about 6 months ago | (#46662599)

"Science Vulcan directorate has determined that time travel is....... not fair"

I have always been suspect of the the idea "god" would allow little "pissants" like us to have quantum computers with thousands or tens of thousands of entangled qbits... to me it seems too good to be true no different than pulling energy out of nothing.

Such feelings might inform a career path or assumptions about concepts currently out of reach of ones ability to experimentally check however they should never be confused with reality.

Scott Aaronson's take (3, Funny)

JoshuaZ (1134087) | about 6 months ago | (#46662619)

Scott Aaaronson is a highly respected quantum computing expert at MIT. His initial reaction at comment# 89 at http://www.scottaaronson.com/b... [scottaaronson.com] is that "The abstract of that thing looked so nonsensical that I didn’t make it through to the actual paper. If anyone has and wants to explain it here, that’s fine." Given that I wouldn't take this too seriously.

P is not equal to NP (1)

Anon-Admin (443764) | about 6 months ago | (#46662693)

Well of course P is not equal to NP. That was proven with PiV where PiA and PiM may be an indication of P on P but in some instances indicates P on NP. Just goes to show that PiV is proof that P is not equal to NP. Especially where s is a sub of D. ;P

Maybe the universe is better than us (1)

KramberryKoncerto (2552046) | about 6 months ago | (#46662947)

Even if the proofs are true, the physical implications were drawn too far. It doesn't account for the possibility that quantum effects do involve (super-)exponential classical computation; that the universe doesn't care if its rules can be enforced "efficiently" by a Turing machine.

Bullshit (0)

Anonymous Coward | about 6 months ago | (#46662987)

> And because all NP-hard problems are mathematically equivalent
This is bullshit. NP-hard problems are not equivalent. NP-complete ones are

The author's are confused about physics (0)

Anonymous Coward | about 6 months ago | (#46663007)

QM is a mathematical model and description of certain empirical data. Schrodinger's equation is something that human's (or things intelligible to humans) solve. The universe doesn't solve things. It doesn't even not solve things. The whole notion is incoherent without some new technical definition of "universe".

A link between QM and P/NP could be interesting in terms of our limits, as humans; but it doesn't imply that macroscopic entities are necessarily classical at some limit. That doesn't even begin to make sense.

According the Actual Paper... (5, Funny)

careysub (976506) | about 6 months ago | (#46663065)

The summary is actually accurate! [arxiv.org] This was quite a surprise to me, since as many other posters have correctly commented here, these claims are absurd. The Universe is not inconvenienced by the difficulty of computing something about its properties.

Perhaps this paper should have been released two days ago.

Hmm... the Incomputatibility of the Universe, maybe this is an avenue for proving the the Universe is not a simulation?

Re:According the Actual Paper... (1)

careysub (976506) | about 6 months ago | (#46663101)

Perhaps this paper should have been released two days ago.

Errr... make that three days ago.

Its called GOD (0)

Anonymous Coward | about 6 months ago | (#46663117)

GOD is NP Hard but resolves all issues in all sub domains and on all scales before the problem is even expressed as an emanation of electromagnetic flux. The math is complex and carried out by the sum total of all potential dimensions and universes and their interactions as factors of pure self awareness, none such driving from same.
The granular consistency of black holes marches on as being and non being interpolate across anode planes.

Not hard with an analog computer (0)

Anonymous Coward | about 6 months ago | (#46663139)

I made an analog computer to solve this problem.
I put a cat in a box with a timer and cyanide, and when I opened it, the cat was alive.
Likewise with other macro assemblies, they are each their own analog computer.

joking aside,
I have to wonder if where this paper is eventually going is to be somehow related to the idea that the universe is some kind of a digital program running on a large computer in a super-universe. If you can prove that this universe is non-solvable, then you can safely say that our universe is not a simulation.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>