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!"
Schrodinger's cat is definitely dead. Chewbacca ate it.
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.
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.
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?
P is equal to NP only if N=1. Voila!
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
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
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.
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!
Macroscopic outcome of quantum effects can be observed every day. Every chemical reaction and every electronic operation are macroscopic outcomes of the Schrodinger equation.
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.
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.
Isn't the radiation monitor an observer?
A natural process cant compute.
"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.
It could just as easily mean that quantum computers will be able to solve NP-Hard problems efficiently.
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.
Yes, it is hard to solve TSP on a classical computer, but NP-complete problems can be solved efficiently on a quatum computer...
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.
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.
Some drink at the fountain of knowledge. Others just gargle.
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".
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.
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.
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
"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.
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.
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 Heaven is just a better simulation...
Very easy. Make the universe throw a BUS ERROR. Then you know.
Thinking about it, maybe Black Holes are indeed the same as a bus error.
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?
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
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.
> And because all NP-hard problems are mathematically equivalent
This is bullshit. NP-hard problems are not equivalent. NP-complete ones are
I wonder how many universes end when their inhabitants cause a fault in the code and their designer fails his simulation class.
"I opened my eyes, and everything went dark again"
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.
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
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.
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.
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.
"Solved" (computed) by humans or by the "mechanisms" of the universe?
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".)
Table-ized A.I.
Have we figured out why the physical laws that we know about exist yet? Otherwise in a purely hypothetical scenario we cannot rule out anything. We are not even certain that the laws that we have have always been stable or why.
What we can do is just build of what we can until we reach the point that we can make a reasonable guess. Caveat. It is somewhat unreasonable to think that I am Indy in another universe.
The real question there is why not?
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.
Black holes are large-scale pot-holes. Perhaps us planets are not paying our taxes. The Ferengi want the free market to fix them and skip payment.
Table-ized A.I.
Computational complexity refers to the asymptotic behaviour of the function. If the size of the input is bound (as is the case for all real world problems such as the state of a cat), solving it is an O(1) problem - just may take a while depending on your computational device. Surely a computer big enough (as in, bigger than the system you are trying to solve for) can solve the equation and make predictions.
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.
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.
The physics teacher was quoting Samuel Johnson, who kicked a rock and stated "Thus I refute Berkeley" (who had argued that we can't know whether any material objects actually exist) : http://www.samueljohnson.com/r...
It's not clear what Johnson thought he'd proved by that.
http://www.geoffreylandis.com
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.
100 years? No, that's not how these problems scale. If it isn't P, then a macroscopic object (like the cat) is beyond our ability to simulate using deterministic Turing machines, period. The universe will not be habitable that long. Think about how many particles are involved, then realize that the algorithm scales exponentially. Even if our computers get a million times faster someday - so what, that's still not nearly enough. So, either we find a way to build fast and scalable nondeterministic Turing machines (we're nowhere near that goal) or the model is useless for macroscopic objects.
It's called "The Simulation Problem" and is best explained in Ian M. Banks scifi novel "The Hydrogen Sonata"
Basic
Understanding
Limiting
Logical
Solutions
Heaped
In
Theory
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
"So if macroscopic superpositions exist, there must be an algorithm that can solve this NP-hard problem quickly and efficiently." Really? The two aren't related. Does whoever wrote this live in Colorado? This story is wrong on so many different levels that it's hard to know where to start. Like it's just a string of phrases all strung together, in the hopes that the writer, if they can't dazzle with their brilliance, at least baffle with their BS...
-- Ed Carp, N7EKG erc@pobox.com PGP KeyID: 0x0BD32C9B What I'm up to: http://intuitives.mine.nu
That sounds right to me. If you are inside a simulation then the simulation is all the reality you have access to. If the universe around you that you have the direct ability to interact with isn't reality, then what is?
In our world, 2 body gravitational physics is a simplicifaction that sometimes helps, sometimes doesn't. If my Kerbals become self-aware, that is no simulation to them, that really is how physics works.
We can make low energy transfers to the moon by taking advantage of the dynamics multiple simultaneous pulls; because 2 body gravity is only a simiplification for us.... they will never get to the Mun that way....it just doesn't happen. No matter what experiment they do, they will never find evidence of multiple body gravitation.
"I opened my eyes, and everything went dark again"
...I want to punch someone.
(I blame "The Tao of Physics" for instilling this basic drive in me.)
"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."
There will always be some Bill Murray ruining it.
Okay, but is it all-or-nothing? It may be possible to get pretty-darn-close approximations using undiscovered short-cut techniques. Thus, even if theoretical perfection in computation is not possible, practical (good enough) simulation may be.
Further, maybe someday quantum computers will be able to tap into parallel dimensions and/or time-scapes in order to get computers bigger than OUR (known) universe. We don't really know what the upper bound is.
Table-ized A.I.
I had been hoping that my girlfriend could be solved in polynomial time, but now I suspect she is NP hard.
From the summary, it sounds like this theory is saying that a quantum computer is useless, or that it cannot be scaled up, because something in quantum mechanics is preventing a quantum computer from efficiently calculating an NP problem.
But it asks the question, what is the reason for this computational limit? It's not like atoms are actually using computer algorithms to calculate their behavior.
just not the macroscopic world.
1) The article is dumb.
2)
And because all NP-hard problems are mathematically equivalent
You mean NP-complete.
I only read through the summary at https://medium.com/the-physics... but it seems like he is implicitly assuming that the universe is (or is equivalent to) a simulation running on a classical computer.
Ah the dangers of long forgotten assumptions....
Given this, would you actually need to restart it? I mean, if universe is deterministic, then all future and past is already contained in a description of its initial conditions. You'd only need to run the simulator if you wanted to observe or communicate with the people inside; otherwise, as far as they (we) were concerned, why would actually crunching through those numbers have any effect?
But of course, if you're not going to run a simulator, there's hardly much point in uploading it to a computer, now is there? So simply write down your initial conditions and rules of evolving them. That should be enough for us. Except, of course, your pen is not magical, so simply writing anything shouldn't cause a universe to exist; but if it doesn't, then merely existing in whatever sense mathematical concepts exist should be enough to "create" all their possible consequences, including us.
Metaphysics is fun at 3 AM :).
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
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.
Beautiful Picture!Amazing!
http://de.mon.st/RyEq2/
Lets assume that there is an NP-hard formula for a system that describes its evolution relative to a "system time" variable. Why assume that the "computation time" it takes to solve that formula is related to the "system time"? If its unrelated, then an infinite amount of "computation time" (as in the number of real numbers between 1.0 and 2.0) can be used to compute the state of the system at the next "system time" tick, followed by another infinite amount of time for the tick after that and so on. The computation of the system evolution is not itself a parameter of the system. In other words, if the universe is a simulation run on a Turing machine, we can't tell how long the machine ran to calculate the universe's new state after (say) 10**-30 seconds of system time has elapsed.
Here's a paper about the wave function and computability (computability beyond P, NP, etc)
Marian Boykan Pour-El and Ian Richards. The wave equation with computable initial data such that its unique solution is not computable. Advances in mathematics, vol. 39 (1981), pp. 215–239.
http://www.sciencedirect.com/s...
Review at
http://journals.cambridge.org/...
http://stephan.sugarmotor.org
... they are simply misidentified and called ghosts, magic, etc. depending on the manifestation. They are also called pseudoscience.
So the challenge is: identify clearly what macroscopic superpositions would/should look like and how can we experimentally create/detect them.
"Consensus" in science is _always_ a political construct.
I think the quantum eraser experiment is a strong indication that our universe is (lazy) computed.
A photon shot at double slit is a wave.
But only if you do not measure which slit was taken.
Or if you do measure: only if you destroy the measurement result.
I think the universe does lazy evaluation on which slit is taken.
If the result turns out to be 'not used' then the computation is skipped, and the light is approximated with a wave.
So not only is it a sim, the extra dimensional higher order entity running the sim cares about speed of computation.
http://www.stolk.org/tlctc
That's exactly right. I just finished reading the paper. He's basically saying that we don't know what the Schrodinger equation predicts for macroscopic systems, because it's completely impossible to do the calculation and find out. Actually, whether P=NP doesn't really matter as far as that goes. Whether or not it will some day be possible to do the calculation, thus far we haven't done it, so we don't know what the result is. We shouldn't go around making claims about half-dead/half-alive cats when we have no idea whether QM predicts that or not.
There's a bit more to the paper than that. It has two main parts. The first is a proof that solving the Schrodinger equation is NP-hard. He then considers the case of a simple test system (for which we can solve the Schrodinger equation) coupled to a complex environment (for which we can't). He makes some heuristic arguments based on a set of reasonable sounding approximations, and shows that they lead to the standard probabilistic behavior and wavefunction collapse for the test system.
I don't think any of this is really new. It's just a different way of looking at decoherence. Still, it makes interesting reading.
"I'm too busy to research this and form an educated opinion, but I do have time to tell everyone my uninformed opinion."
I thought the NSA already proved P = NP?
"The Navier-Stokes equations were too out-of-this-world to be considered as a special case of general relativity's singularities." -- Anastasia Roupakioti
I would say that physics is clearly a subset of mathematics, which is to say we can pose even simple questions that are outside of physical reality. And, no, the imaginary number i is not what I have in mind. But the fact that there is absolutely NO object in existence that needs the full value of pi suggests that the universe (and the physics thereof) is a subset of mathematics. And P not equal NP may fall into the same crack, which is to say that the universe is too small (and granular) to contain the NP problems that make P not equal to NP.
"There is no god but allah" - well, they got it half right.
Well, Bolotin's reasoning seems fascinating at first sight, but it's worth recalling that there is a VERY strong realist assumption hidden there, namely, that the universe constantly "solves" Schrödinger's equation in order to work. Now that's two subtly (but crucially) different things to say that that: (1) certain properties of our world are well *described* by Schr's Eqn., and that: (2) certain features of the world *depend* on computational properties of Schr's Eqn. What one can say for sure is that Schr's Eqn. is our representation. To say anything stronger than this would require an independent defense of scientific realism (certainly not a trivial task).
As Max Tegmark explains in his book, Our Mathematical Universe, the reason why large-scale superposition does not exist is because of incoherence, or the fact that "observation" destroys superposition. Here, "observation" means any interaction with other particles, such as photons.
I don't think the assumption was that the universe "solves" the equation to "compute" reality. Rather, I think the point was that the "breakdown" of quantum behavior into macroscopic behavior seems to happen around the same scale that the interactions described by Schrödinger's equation start to run into fundamental limits of computability in the form of the Planck Length, and that this can help "explain" the transition to macroscopic behavior as simply being the point at which the system becomes too complicated, in a fundamental complexity theory sense, for Schrödinger's equation to accurately describe it any longer.
if it is a simulation it was programmed by an alien to compute the universe's evolving state based on equations (e.g. Schrodinger equation, relativity, or the underlying unification thereof). Maybe there are bugs in his code that we can detect. Sort of like Skyrim NPCs detecting bugs in Skyrim itself (of which there are many:).
The Three-body problem in classical mechanics is known to not have any analytical solutions at all, let alone computable. Generalized, this means that as the number of material objects, moving under the action of their own gravitational fields, increases above 3, it becomes harder and harder to find out how they would be moving.
That in no way implies that these bodies will become exasperated with computational complexity of their "n-body problem" and decide to simply fly apart.
The Three-body problem in classical mechanics is known to not have any analytical solutions at all, let alone computable. Generalized, this means that as the number of material objects, moving under the action of their own gravitational fields, increases above 3, it becomes harder and harder to find out how they would be moving. That in no way implies that these bodies will become exasperated with computational complexity of their "n-body problem" and decide to simply fly apart.
Judge a man’s idea, not a man. Do not use your own personality in order to explain actions of someone else.