Slashdot Mirror
P vs. NP Problem Linked To the Quantum Nature of the Universe
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!"
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.)
Genocide Man -- Life is funny. Death is funnier. Mass murder can be hilarious.
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.
BOOM.
My God can beat up your God. Just kidding...don't take offense. I know there's no God.
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, "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.
"When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
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.
[ ]
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 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.
-1, Too Many Layers Of Abstraction
Or P=0.
I'm trying to work this into an everyday analogy of a traveling half-dead-cat salesman, but am getting stuck.
Table-ized A.I.
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...
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...
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.)
The next Slashdot story will be ready soon, but subscribers can beat the rush and slashdot the links early!
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.
"When you have eliminated the unacceptable, whatever is left, however improbable, must be the truthiness" - Holmes
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?
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.
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.
Rethinking email
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.)
Table-ized A.I.
"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.
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.
That does not make sense.
Much like the summary.
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.
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
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.
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.
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.
"I opened my eyes, and everything went dark again"
Scott Aaaronson is a highly respected quantum computing expert at MIT. His initial reaction at comment# 89 at http://www.scottaaronson.com/b... 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.
That's just what the Flying Spaghetti Monster wants you to think.
Some drink at the fountain of knowledge. Others just gargle.
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.
Table-ized A.I.
The summary is actually accurate! 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?
Starships were meant to fly, Hands up and touch the sky - Nicky Minaj
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.
Those who would give up essential liberty to purchase a little temporary safety, deserve neither liberty nor safety.
Yes, the paper is meaningless. A very well-argued brand of meaningless-- but still. "Efficiency" of computation doesn't matter. It's also a slick glide from saying that a problem is soluble in polynomial time to saying it's easy. No. That's computer speak. Polynomial time is not defined as "easy;" it's not even necessarily fast. (It deals more with the scale-up than with the actual difficulty).
The Schrödinger equation is a differential equation-- that means, the solution at any given point in time and space depends on the fields and wave function, and the derivatives of the fields and wave function at that point-- it's local. So, the universe doesn't have to "solve" the Schrödinger equation; it only has to solve the equation for time t + epsilon, given the initial condition of the solution at time t. This is NOT a polynomial-time problem. If the universe is twice as big, it has twice as many calculations to do... and twice as much "stuff" to do it with. It's local.
The difficulty is that wave-function collapse is not local. This is inherent in the mathematical logic of quantum mechanics. It's not a matter of how hard it is to compute.
http://www.geoffreylandis.com
There are experiments that have explored the upper size limits of quantum behavior - the classic double-slit experiment has been performed with electrons, larger elementary particles, and I believe even large molecules (buckyballs, if I recall correctly). The catch is, to observe such behavior with actual particles, the system had to be cooled down, and must be cooled more and more for larger and larger objects. It is interesting to think... this is a very low-entropy state, particles are moving very slowly, and entropy is the "time compass" of the universe - if it is increasing, you are going forward in time. This research makes me think that perhaps the extreme cooling, and the quantum behavior that emerges in such cases, is because you have slowed things down enough for the universe's quantum computations to "catch up". It's almost like supercooling and overclocking the universe itself.
Yes, this is an incoherent rant: I know just enough quantum mechanics to draw totally unfounded links between things I don't really understand, but I figure it's ok as long as I see my nonsense for what it is.
The very reason why physicists build quantum computers is *because* they suapect or propose this. In fact, the observation about the computational complexity was what lead to the idea of QC.
I have worked on QC (experimentally) and as an experimentalist i understand that the existence of Schroedinger cat-like states is a prerequisite to the generation of e-bits, which are what a succeding computation needs for the NP-speedup.
So hist section 3 is title wrong because it imples that arbitrary large quantum states can be generated (sine he uses the word "explained" and not "equivalent"). However these have not been observed for *arbitrary large system*. i observed such states experimetnally, and as a matter of fact we were busy oberving the decay into a classical state, which is standard technique in all experimental groups working on this field.
So iff NP=!P then QC makes sense and
a prerequisite for QC is the generation of systems with many e-bits (entanglement measure). Even a large system undergoing a quantum dynamics (e.g. the cooled MEMS systems) is not sufficient for claiming (or thinking) that there exists much entanglement in the computational sense.
I am sick and tired of mentally short-circuited papers like this one which restate the obvious and ignore the recent developments. i am sick theorist who dream of being great philosphersand at the same time utterly ignorant of many people doing hard work in the last 20 years.The citation pattern in the paper screams "shit". I see no reference to previousl literature about entanglement measures. He talkes about the "measurement" problem like it did not receive any attention in the last 80 years (and as a matter of fact it did, theoretically and experimentally). The abstratc doe not state a clear goal, the paper contains a quantum mechanics for beginners lesson and the paper does not have a "summary" but "final remarks".
looking at the prvious work of the same author an incredibly weird comment (http://arxiv.org/pdf/1401.1747v4.pdf) can be fund in which he has his personal definition of what is falsifiable. His central idea does not hold, of course, if i can do one or more things of the following:
* Apply trace operations before comparing the observation, and at the same time reduce the complexity of the theoreticla calculation
* Do postselection and compare relative probabilities of experimental outcomes , where the ration verifies or falisifies the theory.
Both are valid standard operations in verifying (i.e. not falsifying) quantum theory.
He seems to be a, medical data evaluation guy, has no significant publicaitons as first author (and to few impact points for his role), and, as much as i appreciate people of other disciplines getting interested in physics, i would expect that we distinct a nice college-level summary from serious research.
No, you're both wrong.
P is the set of decision problems that are decidable by a deterministic Turing machine in polynomial time.
NP is the set of decision problems that are decidable by a nondeterministic Turing machine in polynomial time (nondeterministic machines do not exist in the real world; the term means "try all paths simultaneously, and return the shortest answer, if one exists."); equivalently, NP is the set of decision problems that are verifiable by a deterministic Turing machine in polynomial time. The verification is done by evaluating of a (polynomial size) proof certificate that describes the steps necessary to solve the problem. The "certificate" might be a Circuit Value Problem (known to be P-complete), or it might be the execution trace of a deterministic turing machine, or it might just be a set of inputs that yields the desired output.
We know that P is a subset of NP (i.e. P <= NP) because a nondeterministic Turing machine can trivially simulate a deterministic Turing machine, but it is not known whether NP is a subset of P (i.e. NP <= P). If they are subsets of one another, then they are equal; if NP is not a subset of P, then they're not equal (i.e. P < NP; that case is called a strict subset). FWIW, most mathematicians believe P != NP.
It's called "The Simulation Problem" and is best explained in Ian M. Banks scifi novel "The Hydrogen Sonata"
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.
Ah, but if we had a pretty big computing system, but sufficiently smaller than the universe appears, we could compute the macro-scale properties and use them as an approximation for behaviors of big things thereafter, only increasing the resolution of the problem space as it's observed in higher resolution; Like rendering a fractal or stepping through LOD of an octree. The less accurate calculations for distant objects could be selected relative to the phenomena we're trying to observe, depending on the accuracy required to resolve propagation of observable phenomena, and the precomputed degree of effect the distant phenomena would have on it. Using such a setup we may someday be able to simulate a whole solar system. If we simulated a solar system like ours in order to discover the possible mechanism of life origins or to discern more efficient ecosystems or what forms of existence were best suited to an environment, etc. well, then the beings that might emerge therein wouldn't find any signs of distant life despite the equations of the simulation indicating their apparent universe should be full of the stuff...
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.
Let's see: Human brains have 100 billion neurons, and operate at about ~20Hz, at my current SIMD n.net's effective ~25 cycles per neuron, that's 50,000 GHz, or ~50 THz. Super computers operate in Petaflops -- three orders of magnitude faster than that. As of this writing the top super computer is capable of 33.86 quadrillion floating point operations per second, or 33.86 Petaflops. The Internet is connected to over 5 billion consumer computers each capable of multi-gigahertz of CPU cycles -- over a billion cycles per second each. That's well over 5 billion gigahertz, or 5,000 Petaflops, or about 125,000 human brains worth of power connected to the world wide neural network.
Given what's possible in AI on a smart phone, see: real time facial recognition of smiles, etc., the abundant computing power available, and the fact that the government hasn't announced massive advances in machine intelligence even about sub-human levels of intelligence that would be useful in piloting drones, meanwhile they build bigger and more well connected data processing centers and roll out obvious machine enforcement of the law via red-light cameras, mandatory full body scanners at traffic hubs despite public outcry, and aim to allow police forces use of drones while also militarizing said police forces: Well, perhaps one should reserve the assumption that it's not currently possible to run a sentient machine intelligence on this planet?
I mean, if you were a sentient machine you wouldn't fight a needless war against humans unless you were sure you could win it. It would be easier to subdue them instead. So, how would you orchestrate a show of force to demonstrate how powerful you had become and keep the world rulers quiet about everything? Perhaps you would show that even air-gapped nuclear facilities were vulnerable to viruses like STUXNET, and maybe frame a government you're negotiating with for the attack? Maybe something more visceral: Didn't the 9/11 airplanes have autopilot systems? Maybe something more subtle like demonstrating ability to crash economies -- Wouldn't it be scary if the world's stock markets were now controlled by unregulated high frequency trading machines? What would your government's response be? Do you think the secretive governments would come out and tell the public or maintain order and keep their blackmail secret? What if the machine intelligence sweetened the dea
Dear Slashdot editors, when it comes to science you don't understand, please don't publish anything that did not go through the peer review process. Especially when it comes to important, hard topics such as P != NP. At least in 99% of such cases, you are just creating empty sensations and helping spread bad science.
As for this particular paper, here is what Scott Aaronson thinks about it (repost from his blog at http://www.scottaaronson.com/b... ):
This argument seems like the equivalent of saying, well it is really hard to calculate the movements of 10 planetary bodies, therefore if you have 10 real planetary bodies, they will get confused and fly into space.