Slashdot Mirror
Pancake Flipping Is Hard — NP Hard
mikejuk writes "French computer scientists have finally proved that sorting pancakes is hard — NP hard. No really — this isn't a joke. Well, it is slightly amusing but that's just because it is being presented as pancake flipping. The algorithm in question is sorting a permutation using prefix reversal — which is much easier to understand in terms of pancakes. Basically you have to sort a pancake stack by simply inserting your spatula and flipping the top part of the stack. We now know that if you can do the this in polynomial time then you have proved that P=NP."
...in finding the exact amount of maple syrup I need to pour on a pancake stack to ensure that my bacon is accidentally covered in it.
Because I would never intentionally put maple syrup on my bacon; that's barbaric.
How we can do it in polynomial time but computers can't?
Sounds like they just reworded the Towers of Hanoi puzzle, which has been around for a long time.
I love this problem. I have been reading about P=NP blah blah blah but never had a solid mental picture. This is great. I get it. Thanks. I wonder how many other mathematical misunderstandings could be cleared up with something as simple as pancakes?
I really like this example because it is so intuitive. Its obvious at a glance that 2n is the worst things could ever get (they say 2n -6 for n >= 16) .. the real problem is, when it is easier than 2n (not from trivial already in-order sections), how do you find the optimum? :)
Now if they can only explain to me what the hell 'polynomial time' is.. maybe with a bagel allegory..
Bill Gates' only published paper gives a solution to the pancake-sorting problem. I discuss it at my blog.
And what did you expect on a site that has the tagline "News for nerds, stuff that matters"?
Clarification from the article, the actual problem statement is:
The question to be answered in both cases is, if the stack has n pancakes, what is the maximum number of flips needed as a function of n, i.e. f(n)?
With regards to actual doing this for a specific stack, it's fairly trivial to order the pancakes in a polynomial number of flips (any n log n sort algorithm would be fine - with the actual flipping taking at most 2 flips per pancake).
Let's not stir that bag of worms...
The fiddly part is that the question is what is the minimal number of flips required to sort the stack. Finding some number of flips that will sort the stack is fairly straightforward.
Assume we are stacking pancakes with largest at the bottom.
To me, assuming that you consider "Find the largest unsorted pancake" to be O(N), the algorithm is O(N^2). Number of flips is 2N. Where's my turing award?
So I must be missing something... Is one not able to find the largest unsorted pancake easily? Perhaps you are only able to look at the size of the topmost pancake. The article was unclear.
-- Erich
Slashdot reader since 1997
It's worth noting that sorting the pancakes in polynomial time is easy.
From wikipedia: "The simplest pancake sorting algorithm requires at most 2n - 3 flips. In this algorithm, a variation of selection sort, we bring the largest pancake not yet sorted to the top with one flip, and then take it down to its final position with one more, then repeat this for the remaining pancakes."
It's computing the optimal sequence of flips in polynomial time for any given stack of pancakes that's NP-Hard.
There is a pancake flipping algorithm. Have you heard of it?
Seriously, pancake flipping has been around forever. Seriously, its one of the few algorithms that even Bill Gates has implemented: http://en.wikipedia.org/wiki/Pancake_sorting#History And apparently the co-creator of Futurama has as well.
TFA mentions that they proved pancake flipping was NP-Hard. Cool. THATS IT. It doesn't explain how they got to this conclusion, it doesn't explain the significance, it doesn't extrapolate anything useful...
Cool story bro.
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
That tag line has been gone for a few months. Just FYI.
Seven puppies were harmed during the making of this post.
There seems to be a miscommunication here. You can prove that P = NP only if you can solve an NP-complete problem in polynomial time (or some other type that can be reduced to every other problem in the set). The article refers to NP-hard, which is not necessarily in the NPC set. Thus, solving the pancakes problem in polynomial time only guarantees that P = NP for the pancake problem (again, unless you can reduce it to every other problem).
No need to get the fucking Belgians involved in this ok? Europe is in enough trouble already.
Seven puppies were harmed during the making of this post.
It's still there for me? go to slashdot.org, see browser tab heading
Oh yeah you're right. But it used to say "News for nerds, stuff that matters" under "Slashdot" in the top left corner. That's gone.
Seven puppies were harmed during the making of this post.
The more important question is knowing when to flip the pancake.
http://alternatives.rzero.com/
Here's the paper: http://arxiv.org/pdf/1111.0434v1
You must be new here too.
A slashdotter would know where to search for the UIDs and what would 7 digit UIDs would mean.
We are French. We take Cooking seriously. Therefore, all our crepe are perfectly sized. There is no need to sort them. If they are French, they are properly sized!
(Now, that's the theory, but it does not happen in my kitchen.)
From the Pancake Institute: "Fuck Waffles"
Light travels faster than sound. This is why some people appear bright until you hear them speak.........
Comment removed based on user account deletion
The hard part is finding the optimal solution with the fewest number of flips.
Comment removed based on user account deletion
That was my first thought. It took a bit to realize the problem is not sorting the pancakes, but finding the optimal sequence of flips to sort the pancakes.
You need to think in terms of "what's the fewest number of flips required for any possible permutation of size n."
(Hint: The problem is hard because there are n! permutations.)
p.s. I'm still half-asleep, so I haven't completely convinced myself that the correct decision problem at hand isn't Sigma-2 (aka NP^NP, or ExAy F(x,y)) or Pi-2 (aka Co-NP^NP, or AxEy F(x,y)) rather than Sigma-1 (aka NP, or Ex F(x)). Will someone please take a stab at writing the decision problem? Right now the best I can come up with is: "Is there a permutation of size n that cannot be sorted with at least k <= O(n) flips?", and that's clearly Sigma-2 (exists permutation such that for all re-orderings of size <= k, reordering is not sorted). I know I'm missing something obvious here...
A different type of food.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
Who sorts pancakes? Why is there any need to flip pancakes already in a stack? Who jams their spatula into the middle of the stack? WHAT?!
"Love heals scars love left." -- Henry Rollins
I know I really shouldn't read slashdot when half drunk and blurry eyed but fine, I will take your advice and in future get my maple syrup from Canadians. Anyone got a large press for sale? Funny, I always thought it came from trees but then that was before I learned about the duck press.
MMO Quests are like orgasms:
You may solo them, I prefer them in a group.
Beetlejuice was distributed by Warner Bros., which got bought by HBO's parent company shortly after the film was released. CBS owns Showtime. So wouldn't the product placement be HBO this time?
The entire article should be thrown out, it doesn't say anything useful at all.
Also, if you thought that ANY solution of pancake flipping would win you a million dollars, you need to have your head examined. The problem obviously has more to it than that.
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
Re-reading the summary, you're right, its extremely misleading. Lets toss out the summary AND the article! Bad /., bad!
GCS/MU/P d- s:- a-- C++++$ UL++ P+ L++ E+ W++ N o K- w--- O M+ V- PS+++ PE Y+ PGP t+ 5- X R++ tv+ b++ DI++ D++ G+ e++ h-
Explanation denied. I've sat at many a nerd table at IHOP. They were never armed with a spatula and they never sorted any damn pancakes.
"Love heals scars love left." -- Henry Rollins
Comment removed based on user account deletion
Galettes flipping, even. And theres no such thing as maple syrup. Honey and apples all the way!
There's nothing like $HOME
And butter. How could I forget butter? I'm losing a lot of Breton creds on this one...
There's nothing like $HOME