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"?
Shouldn't it be crepe flipping?
We already know P = NP when N = 1 and P = 0.
OK. Now we can discuss the article.
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...
any reason to think this isn't just another bogus complexity paper on the arxiv? has anyone credible verified this?
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-
Am I missing something? Not only is this solvable in polynomial time, it's a trivial polynomial.
Building your stack up from bottom to top, you use the following algorithm:
1. Any time all the pancakes on the bottom are in the correct position, you never touch them again. Consider the "stack" to start just above the highest pancake that's in the correct position.
2. Any time the pancake that would otherwise go in the next position on the stack is at the top, you flip the entire stack (excluding, of course, all the ones from #1 above).
3. In all other cases, insert your spatula just below the pancake that should go next on the stack, flip that much of the stack, which puts it at the top, reducing this problem to #2 above.
Bonus: If you want your pancakes burnt-side down, when you get to step 2, if it's already burnt-side down, flip only the top pancake before proceeding.
So at maximum it takes 2 operations to move a pancake into position. One to put it at the top, one to flip the stack. In other words, the maximum number of operations is 2*N. For the burnt-side-down variation, 3*N.
What am I doing wrong here?
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).
The problem described in the summary is easy: In each step flip to bring the largest pancake that has smaller ones below it to the top and then flip once more to put it to its final position. The problem that TFA claims is NP-Hard is a variant of the above, where all the pancakes are burned on one side and you have to finish the sort with all the burned sides face down.
You must be new here
Real men have 2 frying pans and just empty the pancake in to the other one by roofing the first pan with the second, then turning them around.
We'll be having none o' that fancy flipping stuff in my house, they are as bad as birds being all flying and defying gravity, IT'S NOT NORMAL.
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.
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...
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
Reference 6 in the paper refers to work by Futurama creator David X Cohen (David S Cohen at the time of the publication). As noted in the Wikipedia article about Dave, his most notable publication was on pancake flipping, although Dave's work related to the burnt pancake problem in which the pancakes are to be flipped so all the burnt sides face down. Dave is also a personal friend of mine and so my own brush with fame. I will suggest that Bender flip some pancakes in honor of this paper. I am sure Dave will quietly ignore the suggestion, since he is quite polite.
Pancake flipping problems have been around for a while. The book "Programming Challenges" features one, and notes amusingly that pancake flipping was the subject of Bill Gates' one research paper while he was in school. (It's pretty easy to find on Google.)
The most amazing fact about pancake flipping related problems is: Who was one of the pioneers in that domain with a 1978 paper ? Ok, don't tell me that you are reading slashdot and don't know the answer.