Do you have adblock enabled?
 
If you can read this, either the style sheet didn't load or you have an older browser that doesn't support style sheets. Try clearing your browser cache and refreshing the page.

(Medium)   Schrodinger's Cat caught, fried and eaten by P vs NP problem   (medium.com ) divider line
    More: Interesting, quantum, physics, nurse practitioner, universe, Schrodinger, NP problem, quantum superposition, wave functions  
•       •       •

3033 clicks; posted to Geek » on 07 Apr 2014 at 9:53 AM (2 years ago)   |   Favorite    |   share:  Share on Twitter share via Email Share on Facebook   more»



44 Comments     (+0 »)
 
View Voting Results: Smartest and Funniest
 
2014-04-07 09:58:23 AM  
There has got to be something lost in translation between the person doing the work and the person reporting it, because the way that it's being described in the article sounds like saying "There is no way in hell that we'd ever be able to figure out with certainty the absolute shortest path between all cities on Earth even if we worked at the problem for a billion years, therefore there is no shortest path."
 
2014-04-07 09:58:47 AM  
And with this, abb3w proves the nonexistence of the Flying Spaghetti Monster.
 
2014-04-07 10:01:31 AM  
So the cat had to go pee?
 
2014-04-07 10:03:54 AM  
upload.wikimedia.org
 
2014-04-07 10:04:19 AM  

Delta1212: There has got to be something lost in translation between the person doing the work and the person reporting it, because the way that it's being described in the article sounds like saying "There is no way in hell that we'd ever be able to figure out with certainty the absolute shortest path between all cities on Earth even if we worked at the problem for a billion years, therefore there is no shortest path."


Thanks - that's a nice summary way of stating it.

I was also bothered by this: What's interesting about NP-hard problems is that they are mathematically equivalent. So a solution for one automatically implies a solution for them all.
I believe that's only true for NP complete problems, and P=/=NP implies that "NP-hard" =/= "NP complete".
 
2014-04-07 10:07:36 AM  
Nobody knows why we don't observe these kinds of strange superpositions in the macroscopic world.

Actually, we have a very good idea why we don't observe these kinds of superpositions in the real world. Once a particle interacts with a quantum system, the system slips into a defined state. One stray gamma ray is enough to force the system into a defined state.

Now, it is interesting to think about quantum mechanical operations as computational operations, because that does put boundaries on how quantum systems can behave (the quantum variation on the halting problem puts boundaries on what physical predictions we can make). But there's a lot of "putting the model before the reality" in this post, and reading the sidebar comments is kind of hilarious, as they correct the OP.
 
2014-04-07 10:25:04 AM  
pbs.twimg.com

/Just because I can. Big whoop. Wanna fight about it?
 
2014-04-07 10:35:10 AM  
Also Schroedinger's Cat was meant to be an example of how the superposition theory of Quantum Mechanics had to be ludicrous. It was sort of an *attack* on the probablistic interpretation of quantum mechanics.

/Then we discovered that q-mech WAS almost certainly probabilistic when we showed there wasn't/couldn't be any local 'hidden variable'.
//I admit I'm a physicist and locality/non-locality still gives me issues.
 
2014-04-07 10:45:09 AM  

Delta1212: There has got to be something lost in translation between the person doing the work and the person reporting it, because the way that it's being described in the article sounds like saying "There is no way in hell that we'd ever be able to figure out with certainty the absolute shortest path between all cities on Earth even if we worked at the problem for a billion years, therefore there is no shortest path."


I think there is, but I'm just guessing. My guess is that the original paper said something along the lines that a quantum state is the Universe doing the "sum over all paths" method that Feynman laid out, and can, at most, do "calculations" at the planck scale. If that's the fastest that the Universe can generate solutions for a quantum system, then any system with a brute force calculation time of greater than X (you'd have to have some real good support for why your choosing that time scale) has to collapse the wavefunction and become a macro-scale system.

Or I could be totally wrong, and the article, while interesting, has absolutely no bearing on the actual universe, and just on what we are capable on analytically describing.
 
2014-04-07 10:52:59 AM  

Felgraf: Also Schroedinger's Cat was meant to be an example of how the superposition theory of Quantum Mechanics had to be ludicrous. It was sort of an *attack* on the probablistic interpretation of quantum mechanics.

/Then we discovered that q-mech WAS almost certainly probabilistic when we showed there wasn't/couldn't be any local 'hidden variable'.
//I admit I'm a physicist and locality/non-locality still gives me issues.


Getting a cat into a box is easy. There's no locality problem.
 
2014-04-07 10:59:39 AM  

CheapEngineer: [upload.wikimedia.org image 400x168]


I was going to post that dammit.

/too slow
 
2014-04-07 11:01:16 AM  
This looks like a job for Fraa Jad
 
2014-04-07 11:11:50 AM  

nmrsnr: Delta1212: There has got to be something lost in translation between the person doing the work and the person reporting it, because the way that it's being described in the article sounds like saying "There is no way in hell that we'd ever be able to figure out with certainty the absolute shortest path between all cities on Earth even if we worked at the problem for a billion years, therefore there is no shortest path."

I think there is, but I'm just guessing. My guess is that the original paper said something along the lines that a quantum state is the Universe doing the "sum over all paths" method that Feynman laid out, and can, at most, do "calculations" at the planck scale. If that's the fastest that the Universe can generate solutions for a quantum system, then any system with a brute force calculation time of greater than X (you'd have to have some real good support for why your choosing that time scale) has to collapse the wavefunction and become a macro-scale system.

Or I could be totally wrong, and the article, while interesting, has absolutely no bearing on the actual universe, and just on what we are capable on analytically describing.


This theory seems like it treats the Simulation Hypothesis as an underlying assumption.
 
2014-04-07 11:15:07 AM  

Felgraf: Also Schroedinger's Cat was meant to be an example of how the superposition theory of Quantum Mechanics had to be ludicrous. It was sort of an *attack* on the probablistic interpretation of quantum mechanics.

/Then we discovered that q-mech WAS almost certainly probabilistic when we showed there wasn't/couldn't be any local 'hidden variable'.
//I admit I'm a physicist and locality/non-locality still gives me issues.


The locality/non-locality resulting in quantum entanglement was also also originally an attack on quantum mechanics, the EPR Paradox, but became a key component for applications like quantum computing.  Also there is no limit required for quantum mechanics.  Using the Schrodinger equation to solve for macroscopic things works just fine when you use typical mathematical approximations the results just become negligible.
 
2014-04-07 11:17:34 AM  

HenryFnord: Felgraf: Also Schroedinger's Cat was meant to be an example of how the superposition theory of Quantum Mechanics had to be ludicrous. It was sort of an *attack* on the probablistic interpretation of quantum mechanics.

/Then we discovered that q-mech WAS almost certainly probabilistic when we showed there wasn't/couldn't be any local 'hidden variable'.
//I admit I'm a physicist and locality/non-locality still gives me issues.

Getting a cat into a box is easy. There's no locality problem.


Sometimes it's not so easy:
media1.giphy.com
/hot
 
2014-04-07 11:21:33 AM  
Meh. Sounds either like 1) a reporter trying to describe something they don't understand and failing or 2) a theoretical mathematician trying to assert something about reality purely on the basis of logic system structure in lieu of actually looking at reality. Either way, the article I just read makes a series of claims I find unconvincing and already disproved in certain instances.
 
2014-04-07 11:24:54 AM  

t3knomanser: Nobody knows why we don't observe these kinds of strange superpositions in the macroscopic world.

Actually, we have a very good idea why we don't observe these kinds of superpositions in the real world. Once a particle interacts with a quantum system, the system slips into a defined state. One stray gamma ray is enough to force the system into a defined state.

Now, it is interesting to think about quantum mechanical operations as computational operations, because that does put boundaries on how quantum systems can behave (the quantum variation on the halting problem puts boundaries on what physical predictions we can make). But there's a lot of "putting the model before the reality" in this post, and reading the sidebar comments is kind of hilarious, as they correct the OP.


I should have read down before commenting, as you managed to convey the gist of what I did with far greater simplicity :/ And, now that I've read the sidebar, I see the article's commenters mostly handled all this already.
 
2014-04-07 11:27:04 AM  

Cthulhu_is_my_homeboy: This theory seems like it treats the Simulation Hypothesis as an underlying assumption.


Not exactly. It assumes that the limitations that apply to theoretical computational constructs can't be bypassed by physics. You can't mathematically describe a Turing Oracle, and therefore you can't build a Turing Oracle in the physical world. Or, in this case, you can't solve an NP-complete problem in P time, even if your computer is a physical device.

satanorsanta: The locality/non-locality resulting in quantum entanglement


Maybe it's because I'm a programmer, but entanglement has always made intuitive sense to me. Oh, the state of this particle is dependent upon the state of that one? Okay, so it's like a closure, then. Makes perfect sense.
 
2014-04-07 11:55:26 AM  

t3knomanser: Cthulhu_is_my_homeboy: This theory seems like it treats the Simulation Hypothesis as an underlying assumption.

Not exactly. It assumes that the limitations that apply to theoretical computational constructs can't be bypassed by physics. You can't mathematically describe a Turing Oracle, and therefore you can't build a Turing Oracle in the physical world. Or, in this case, you can't solve an NP-complete problem in P time, even if your computer is a physical device.


Is that a sound assumption? Isn't there another possibility that physical devices can solve NP-complete problems in P time, but there's no way for the answer to be observed with 100% accuracy in P time?

Sort of like how entanglement allows states to propagate faster than the speed of light, but it's impossible to actually communicate information FTL that way because of the way observing those states works.
 
2014-04-07 11:55:27 AM  
Eh, I hate cats. Just keep the box closed.
 
2014-04-07 11:59:40 AM  

4of11: Isn't there another possibility that physical devices can solve NP-complete problems in P time, but there's no way for the answer to be observed with 100% accuracy in P time?


Think about what you're claiming there. You're claiming that there is a physical system that cannot be described mathematically (or that our understanding of mathematics is fatally flawed). That's going way beyond Godel and treading into "physics is broken" territory. It  could be true (it probably isn't), but that's a far more radical assumption, given what we've seen thus far.
 
2014-04-07 12:04:55 PM  

4of11: Is that a sound assumption?


Sound in what way?

It's certainly a possible way the Universe could function, so it is (as far as I can tell) sound in that it does not lead to contradiction. The Universe absolutely doesn't have to work that way, so it is unsound as far as it being a necessary assumption for anything else in physics so far.

We make all kinds of assumptions about the Universe that don't necessarily have to be, but we haven't seen any contradiction yet. We assume there are no magnetic monopoles for Maxwell's laws. We assume that intertial mass and gravitational mass are equivalent for Newton's equations. These don't have to, on any fundamental level, be true, but we have seen no evidence that it's not how the Universe works, so we assume that it is.

This assumption, if it proves useful to explaining certain observable phenomena, will become just another in a long line of assumptions that, when asked about, scientists just shrug and say "that's how the Universe made it."
 
2014-04-07 12:05:38 PM  

Felgraf: Also Schroedinger's Cat was meant to be an example of how the superposition theory of Quantum Mechanics had to be ludicrous. It was sort of an *attack* on the probablistic interpretation of quantum mechanics.


I had thought that Schroedinger's Cat was meant to illustrate the fact that quantum mechanics works on the particle scale, but not on the macro scale?
 
2014-04-07 12:11:01 PM  
Does this mean that Deepak Chopra will finally shut the hell up about his quantum woo?

/Probably not, sadly.
 
2014-04-07 12:13:43 PM  

t3knomanser: 4of11: Isn't there another possibility that physical devices can solve NP-complete problems in P time, but there's no way for the answer to be observed with 100% accuracy in P time?

Think about what you're claiming there. You're claiming that there is a physical system that cannot be described mathematically (or that our understanding of mathematics is fatally flawed). That's going way beyond Godel and treading into "physics is broken" territory. It  could be true (it probably isn't), but that's a far more radical assumption, given what we've seen thus far.


What if physics is capable of non-determinism? I.e., the physical device non-deterministically chooses the correct answer, but we can't observe that answer with 100% accuracy without performing a non-polynomial-time deterministic process. Wouldn't this fall under known mathematics, and violate the assumption you stated?
 
2014-04-07 12:20:15 PM  
24.media.tumblr.com
 
2014-04-07 12:57:53 PM  
The simulation in which we live is run at time dilation so that it is not possible to simulate itself from within.
 
2014-04-07 01:04:39 PM  

Delta1212: There has got to be something lost in translation between the person doing the work and the person reporting it, because the way that it's being described in the article sounds like saying "There is no way in hell that we'd ever be able to figure out with certainty the absolute shortest path between all cities on Earth even if we worked at the problem for a billion years, therefore there is no shortest path."


I'm simplifying this because there are some computational enhancements, but I think the basic problem is a better example.

the travelling salesman problem is an O(n!) problem in it's simplest state. In order to figure out the fastest route between 3 places, it takes 6 calculations: (ABC ACB BAC BCA CAB CBA ignoring the fact that you don't need to do the inverses. I'm trying to make this as simple as possible. )

so O(4!) is 4! = 24.  add one more stop, and it makes it 5!=120. 6! makes it 780, and it goes up incredibly fast from there. Even assuming O(n!/2) it grows tremendously incredibly quickly

There are according to some random website, 2,896 cities over 150k people, The number of calculations necessary would be  http://www.numberempire.com/factorialcalculator.php?number=2896

Adding smaller cities, I saw 36722 on another random website, but I think that's good enough.
 
2014-04-07 01:25:36 PM  
Soon to be an xkcd comic with, perhaps, a stick figure cat.
 
2014-04-07 01:40:44 PM  
There will never be a thread more appropropriate for abb3w
i224.photobucket.com
 
2014-04-07 01:56:15 PM  

4of11: What if physics is capable of non-determinism?


Physics  is capable of non-determinism.

4of11: the physical device non-deterministically chooses the correct answer, but we can't observe that answer with 100% accuracy without performing a non-polynomial-time deterministic process


Don't confuse  our sense of "observation" with the quantum mechanical sense. In QM, "observation" and "interaction" are the same thing. If a quantum mechanical system performs a non-polynomial time process in polynomial time, and "leaks" that result (by interacting with another QM system), then you've still proven P=NP. The fact that human beings can't confirm that without performing an NP process is irrelevant. It still happened, even if we can't see it.
 
2014-04-07 02:44:56 PM  
Math is stupid.
 
2014-04-07 02:52:48 PM  
Reality couldn't give a "flying fig" on what we can figure out.

Everything counts,
whether you can believe in it or not...
 
2014-04-07 02:53:32 PM  

t3knomanser: 4of11: What if physics is capable of non-determinism?

Physics  is capable of non-determinism.

4of11: the physical device non-deterministically chooses the correct answer, but we can't observe that answer with 100% accuracy without performing a non-polynomial-time deterministic process

Don't confuse  our sense of "observation" with the quantum mechanical sense. In QM, "observation" and "interaction" are the same thing. If a quantum mechanical system performs a non-polynomial time process in polynomial time, and "leaks" that result (by interacting with another QM system), then you've still proven P=NP. The fact that human beings can't confirm that without performing an NP process is irrelevant. It still happened, even if we can't see it.


Simulating a result isn't the same as computing the result. For example, the n-body problem in orbital mechanics. Past 2 bodies plus 1 negligible body its impossible to predict exactly the final orbits out X amount of time. We can compute each individual second and get really really close, but out hundreds of years small errors creep in. We could build a few planets and really simulate it in reality, and get an exact result, but is that computing the answer?
 
2014-04-07 02:59:31 PM  

MindStalker: We could build a few planets and really simulate it in reality, and get an exact result, but is that computing the answer?


From a button: "Planets are smarter than astronomers, because planets can solve the n-body problem."

/I prefer simulations that run faster than 1 second/second, myself.
 
2014-04-07 03:23:25 PM  
t3knomanser:Physics  is capable of non-determinism.

Physics is known to operate probabilistically, so not according to Newtonian determinism. But that's not the same as full non-determinism in the computational complexity sense. Quantum physics essentially operates on determined probabilities, which is a weak form of non-determinism.

Don't confuse  our sense of "observation" with the quantum mechanical sense. In QM, "observation" and "interaction" are the same thing. If a quantum mechanical system performs a non-polynomial time process in polynomial time, and "leaks" that result (by interacting with another QM system), then you've still proven P=NP. The fact that human beings can't confirm that without performing an NP process is irrelevant. It still happened, even if we can't see it.

Not necessarily. "P=?=NP" is the question of whether deterministic computers can solve all NP problems in poly-time. It is known that  non-deterministic computers can solve all NP problems in poly-time; that's the very definition of the term.

If it were shown that some non-deterministic computational process exists in our physical reality that solves NP-complete problems in poly-time, that still wouldn't prove P=NP, because it would say nothing about what deterministic computers can do.
 
2014-04-07 03:51:03 PM  
I call BS on the premise that we cannot witness quantum superpositions at macroscopic scale.

In fact, I say we CAN witness quantum superpositions at the macroscopic scale. I also say we see them all the time.

Let me give you a famous example from 15 years ago. Back in early May of 1999, everyone was gearing up to see the highly anticipated Star Wars prequel, The Phantom Menace. We were witnessing the movie's quantum superposition of two possible states which were 'suck' and 'not suck'. We were asking ourselves if the movie would continue the glory of the originals or were we going to get a turdburger a la the Christmas special. These questions were discussed in all seriousness since our childhoods memories were at stake. We all went to the movie theatre for midnight showings and for the next two hours we witnessed the quantum state slowly collapse into 'suck'.

Don't get me started on quantum superposition of 'better' and 'worse' in regards to Attack of the Clones.
 
2014-04-07 04:14:26 PM  
4of11:
Not necessarily. "P=?=NP" is the question of whether deterministic computers can solve all NP problems in poly-time. It is known that  non-deterministic computers can solve all NP problems in poly-time; that's the very definition of the term.

Non-deterministic computers are still just figments of our imagination. No one has built one yet. The best we can do is simulate non-deterministic algorithms on deterministic hardware.

What this paper is arguing is that solving Schrödinger's equation is NP-hard. Therefore, the bigger the system, the longer it takes the universe to "solve" the equation for that system within a "reasonable" amount of time.

That "reasonable" amount of time is probably the Planck time (5.39 x 10^-44 s). Smaller systems of particles can have their Schrödinger's equation solved within the Planck time and so operate within quantum mechanics.

At some point the system of interacting particles becomes large enough that Schrödinger's equation cannot be solved in the Planck time and the system then operates within classical Newtonian mechanics.

Anyway, that's what I got out of it. Very interesting work. It also seems to lead credence to the idea that P≠NP and grounds it in physical reality.
 
2014-04-07 04:31:24 PM  
As for macro superpositions go to the politics tab, you can see posts made by people who are quite clearly exhibiting a superposition of every possible state of derp at once.
 
2014-04-07 04:49:14 PM  

nmrsnr: Or I could be totally wrong, and the article, while interesting, has absolutely no bearing on the actual universe, and just on what we are capable on analytically describing.


If we are living in a computer simulation, then deliberately setting up a situation whose outcome requires too much calculation should have some inconsistent effects.  Sort of like how the hair or gowns of Pixar Disney princesses "lock up" if they swirl around too much.
 
2014-04-07 04:50:26 PM  

rdu_voyager: Non-deterministic computers are still just figments of our imagination. No one has built one yet. The best we can do is simulate non-deterministic algorithms on deterministic hardware.

What this paper is arguing is that solving Schrödinger's equation is NP-hard. Therefore, the bigger the system, the longer it takes the universe to "solve" the equation for that system within a "reasonable" amount of time.


Sure, but my point is that the argument only holds if you assume that the universe must actually solve equations in order for its laws to operate, and that it only has the computing power of a deterministic computer to do so. As far as I know, that's not an assumption that's already been established or proven with experimental evidence. The universe  might instead internally operate like a non-deterministic computer which is sufficiently powerful to solve this NP-hard problem in poly-time. Or operating according to physical laws might not be the same as computing the equations that describe those laws.

If this theory turns out to have reliable predictions borne out in experiments, then sure, it could be a good assumption, and one that significantly shapes our understanding of the universe.
 
2014-04-07 05:36:55 PM  
What wonderful nonsense.  I assume that this was published April 1st.
 
2014-04-07 07:00:20 PM  
The algorithm that's running our universe and knows when to switch between quantum and Newtonian physics must be amazing.
 
2014-04-07 11:55:19 PM  

GilRuiz1: There will never be a thread more appropropriate for abb3w


Time to start buying aspirin in bulk again....

I think this guy has two interesting endpoints, which may even be connected, but I'm deeply doubtful about the particular connection he's trying make.
 
Displayed 44 of 44 comments

View Voting Results: Smartest and Funniest

This thread is archived, and closed to new comments.

Continue Farking
Submit a Link »
On Twitter






In Other Media


  1. Links are submitted by members of the Fark community.

  2. When community members submit a link, they also write a custom headline for the story.

  3. Other Farkers comment on the links. This is the number of comments. Click here to read them.

  4. Click here to submit a link.

Report