Pancake Flipping Is Hard — NP Hard 260
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."
I'm more interested... (Score:5, Funny)
...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.
Re: (Score:2)
Re: (Score:2)
My day can now start on a happy note. Thanks for that. :)
Re:I'm more interested... (Score:4, Informative)
Re: (Score:2)
Those are some tasty beetles.
Re:I'm more interested... (Score:5, Funny)
that artificial corn syrup crap the rest of the world calls "maple syrup" that tastes like dead beetles
It's called "beetle juice". It's quite popular in some areas. I love me some beetle juice.
Mmmm. Beetle juice.
Re:I'm more interested... (Score:5, Funny)
Shhh!
You'll summon the remake!
Re: (Score:2)
Re: (Score:2)
Hmmm. Everything also tastes better with bacon. So the question is: does putting real maple syrup on your bacon cause them to improve one another's flavors until your breakfast reaches a maximum recursion limit?
Re: (Score:2)
Re: (Score:2)
Just go to your nearest Whole Foods (or other real food distributor) and get Grade-B maple syrup. It's not as filtered as the standard Grade-A syrup that most are used to. The flavor is incredible compared to the processed crap that everyone is used to.
Re:I'm more interested... (Score:5, Informative)
Just go to your nearest Whole Foods (or other real food distributor) and get Grade-B maple syrup. It's not as filtered as the standard Grade-A syrup that most are used to. The flavor is incredible compared to the processed crap that everyone is used to.
FWIW, maple syrup grades [cookingforengineers.com] are more dependent on when the trees were tapped than on filtering and processing. (Actually, they're most dependent on what state, provincial, or national body is defining the grades, but that's a different story.) Early in the season, trees produce sap that tends to be higher in sugar and water, and lighter in flavor and color. This sap becomes grade A syrup. As the season progresses, the sap tends to become thicker, less sugary, darker, and stronger flavored, eventually becoming grade B and beyond. This varies from season to season and even from tree to tree, but is generally true.
If you're really hardcore about your maple, you can round up some Vermont Grade C syrup, "commercial grade", that's usually used in large-scale baking operations. It's extremely thick and strong -- my wife calls it maple sludge. If you like maple, that's as close to the taste of the tree as you can get without gnawing on some bark.
Re: (Score:2)
I always thought the grading was based on filtering. I learn something new every day!
Re: (Score:2)
I understand not everybody has this luxury, but what I do every spring is shop around in the various friends and families that happen to know people who own or operate a sugar shack and get various grades of maple syrup. I use grade A instead of white sugar for day-to-day usages (coffee, cereals, etc.), grade B when I'm out of grade A or for maple recipes and grade C for maple sauces and dressings. I once had access to grade D and the strength of the taste was incredible, especially in salad dressing.
So y
Re: (Score:2)
I understand not everybody has this luxury,
There's no excuse nowadays. I live in Costa Rica and my local convenience store has "Roland" brand 100% genuine Canadian maple syrup. Of course it costs me like $35 for a tiny little jug, but hey you want good stuff you pay good money. Much better than the "dark ages" (30 years ago) where you could ONLY get maple syrup from Quebec, in Quebec province, and probably had to be able to cuss in French Canadian to get it. Maudit tabarnac.
Re: (Score:2)
Re: (Score:2)
we have both consumer protection laws
Those must be fairly new - it used to be called maple syrup when I was a Canadian ex-pat kid growing up in Florida. I think many restaurants still call it "maple syrup" though on the menu.
And Vermont is very proud of its maple syrup.
Also a recent development. Of course American maple syrup is nowhere near as good as Quebec maple syrup, but that's just my biased Montreal snob-side coming out. Good for you, any cartel (and the Quebec maple syrup industry certainly is a cartel that has been gouging the price for years) deserves a little competition overs
Re: (Score:2)
Re: (Score:2)
And Vermont is very proud of its maple syrup.
Also a recent development. Of course American maple syrup is nowhere near as good as Quebec maple syrup, but that's just my biased Montreal snob-side coming out. Good for you, any cartel (and the Quebec maple syrup industry certainly is a cartel that has been gouging the price for years) deserves a little competition overseas.
I'm not sure where you think Vermont is, but the last I checked from Quebec to Vermont there are no seas, maybe a lake or two, but certainly no bodies of water large enough to constitute calling it a sea.
Re: (Score:3)
I don't know about Maple syrup specifically, but a country's border may very well influence the taste of food simply due to laws banning or prescribing certain production methods of prohibiting the use of certain ingredients.
Re: (Score:2)
It still doesn't make the Canadian's surprise that there is a maple sugar industry south of the Canadian border any less offensive.
And btw, just like in Canada, you /pay/ for the real stuff from NY, VT, NH, and ME.
We had sugar maples growing in our yard in RI. Never tapped them, though.
Seriously, the Canadians here, including you, need to shut the fuck up.
--
BMO
Re: (Score:2)
Even better is maple sugar - it is very hard to find in supermarkets so when I vacation in PA or NH I buy bulk amounts of it. Maple sugar is amazing in breads, coffee, cakes, cookies, and cream cheese frosting. YumYumYum!
No one really eats that "pancace syrup" or "maple flavor syrup" do they? That stuff is nasty.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
And Vermont is very proud of its maple syrup.
Agreed. See here: http://www.theblaze.com/stories/sticky-situation-new-bill-would-make-selling-fake-maple-syrup-a-felony-with-5-yrs-in-prison/ [theblaze.com]
Re: (Score:2)
You can get 32oz. of grade B syrup from Vermont on Amazon for $20. It's what I use for baking.
Re: (Score:3)
That problem is Artery-hard.
This just in!!! (Score:2)
From the Pancake Institute: "Fuck Waffles"
Re: (Score:2)
Even blue waffles?
Has anyone attempted to figure out... (Score:2, Funny)
How we can do it in polynomial time but computers can't?
Re: (Score:2)
Can you? If P!=NP, then logic dictates you will not be able to do it in polynomial time.
That's why they say that if you could do it in polynomial time, then P=NP.
Re: (Score:2)
Am I missing something? I can do it in linear time...
* Start with the bottom pancake and work towards the top
* Locate next pancake, insert the spatula beneath it and flip it to the top
* Insert the spatula at the position where it goes when sorted and flip again.
Number of flips = 2 x Number of pancakes.
Re: (Score:2)
PS: If the pancake is burnt on one side then you just flip it over when it's on the top:
Maximum number of flips to sort burnt pancakes = 3 x Number of pancakes.
Re: (Score:2)
I think the question being asked is, given a certain stack, what is the minimum number of flips required. 2(n-1) is of course an upper bound, but that is not the minimum.
Re: (Score:2)
FTA: "if you can find a polynomial time solution to the pancake problem then you have proved that P=NP."
"f(n) = 2(n-1)" is a polynomial solution of order 1 .... where's my million dollar (and Nobel) prize?
Re: (Score:2)
you haven't accounted for determining the location of the next pancake.
In real life you'd have to do that but the article was about the number of flips.
Re: (Score:2)
Number of compares, not number of flips
Where does it say that...?
Re: (Score:2)
Isn't that what I'm doing?
Re: (Score:2)
Re: (Score:2)
"Polynomial time" does not necessarily mean "quicker than a computer" or even "quickly" or EVEN "slowly". It just means an amount of time proportional to the size of the stack to some power (squared, cubed, etc.)
Just because a human "can do it" doesn't mean that they did it in NP or even P. It just means they did it in a particular time for a particular example. The important thing is "What was that time compared to the size of the data"? I can handsort a stack of one cards just as fast as a computer.
Re: (Score:3)
"size of the problem to some power" is the definition of polynomial time. Polynomial time problems are generally considered "easy" -- for example, your typical sorting algorithm is between n*log(n) and n^2. These grow slowly enough that general polynomial algorithms, even with relatively high exponents (like n^3 and n^4) are doable for reasonably large input sets.
The time it takes to solve an NP-hard problem is more in line with "a constant raised to the power the size of the problem". So doubling the si
Re: (Score:2)
I can handsort a stack of one cards just as fast as a computer.
I don't know why, but I read this as if it said computers had hands...
Re: (Score:2)
I'm struggling to understand the problem, can someone tell me what I've missunderstood.
As I understand it the idea is to sort the pancakes from large to small by flipping a substack. Surely you could apply selection sort, where each time you select a pancake you flip from below it up (resulting in it being on top), and then flip from the place you want to insert it up, resulting in it now being on top of the currently sorted pile.
Clearly as I've just given an easy O(n^2) solution, I've missed something, wh
Re: (Score:2)
So the paper talks about SBPR (sorting by prefix reversals) and MIN-SBPR. The question is not "here, sort this stack of pancakes", it's "determine what the minimal number of flips is to sort an arbitrary stack of pancakes of size n".
If I'm following this, then sorting the stack itself is relatively easy (as you said, n^2). Figuring out the optimal sorting is apparently what's hard.
Re: (Score:3)
it still takes O(n) time to select the pancake to flip.
Re: (Score:2)
Uhhh, no, the proof is that there is no *polynomial time* solution (i.e. all current solutions are higher than polynomial time, like exponential time or factorial time) unless P == NP.
Remember P is the set of problems that can be solved in polynomial time on a deterministic machine, NP is the set of problems that can be solved in polynomial time on a non-deterministic machine.
All problems (even hello world) have a polynomial or higher time complexity (hello world having O(k * n^0) complexity), linear proble
Re: (Score:2)
Re: (Score:2)
Is that, like, you know how to stroke it but it's kinda hard to tell your girlfriend how to do it right?
Re: (Score:2)
Re: (Score:2, Funny)
computers have a specific disadvantage with this problem. they have trouble holding the spatula.
Re: (Score:2)
You can't.
Towers of Hanoi? (Score:3)
Re: (Score:2)
Re: (Score:2)
Erh... like in the Towers of Hanoi [wikipedia.org] problem?
Re: (Score:2)
I think the difference is that there's only one tower, and I assume you can maintain the order of the pancakes in the flipping stack as long as the top pancake doesn't land on a smaller one.
Re: (Score:2)
Re: (Score:2)
Re:Towers of Hanoi? (Score:4, Informative)
For the pancake problem, you only have one pole and you flip as many as you want at once.
Good explanation: http://en.wikipedia.org/wiki/Pancake_sorting [wikipedia.org]
Re: (Score:2)
I thought the same thing, but it is not that close really. The setup is very different in that the plates starts mixed, you only have one pin, but you can move a whole stack of plates in one move.
So not the towers of Hanoi, but the comparison does make it easier for me to see why it could take an exponential number of moves.
Re: (Score:2)
Hmm. This actually means that if you prove this is a reworded version of the Towers of Hanoi, you would have proven N != NP.
I now understand (Score:2)
Re:I now understand (Score:5, Funny)
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?
It's easy: P=pancakes and NP=no pancakes. When P=NP it means you ate them all. The problem is that P-NP != 0 because there's always some maple syrup left on the plate...
Re: (Score:2)
Re: (Score:2)
Conservation of matter dictates that the pancakes are still there.
You have never seen me eat pancakes. I gobble them down so fast that for every m of pancakes I eat, 1/c^2 of e is released.
Re: (Score:3)
long for a good waffle.
Heresy! BURN THE UNBELIEVER!
Re: (Score:2)
Re: (Score:2)
What exactly do you understand now that you didn't before?
Mathematics is complic
Re: (Score:2)
Mathematics is complicated, unfortunately that's just the nature of it, there's no shortcuts. Sometimes ideas can be better communicated through metaphor, but I think you're gotten hung up on the pancakes and as a result you're missing the forest for the trees.
Hmmm. That is an interesting take on metaphor. I was taught that metaphor is the refuge of writers whose thoughts are too fuzzy and undisciplined to be articulated in any other way. Metaphors are for communicating fuzzy ideas, not basic mathematical truths derivable from simple postulates. And no...I don't think mathematics is complicated. If it was complicated, humans couldn't do it. As my favorite author put it,
"Anyone who cannot cope with mathematics is not fully human. At best he is a tolerable s
very friendly np-hard problem (Score:2, Informative)
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? :)
Getting there slowly.. (Score:3)
Now if they can only explain to me what the hell 'polynomial time' is.. maybe with a bagel allegory..
Re: (Score:2)
Re: (Score:2)
you might have explained exponential time with your imprecision
polynomial time: for (n+1)/2 (also known as linear time)
Eating one bagel takes 1 minutes;
eating two bagels takes bagel take 1.5 minutes;
eating three bagels takes 2.5 minutes;
eating four bagels takes 3 minutes;
eating ten bagels takes 5.5 minutes.
polynomial time: for (n^3+n^2+n+1)/4
Eating one bagel takes 1 minutes;
eating two bagels takes bagel take 3.75 minutes;
eating three bagels takes 10 minutes;
eating four bagels takes 21.25 minutes;
eating ten
Re: (Score:2)
I was talking on the phone while responding
here are the correct number:
exponential time (in np if np!=p):for 2^(n-1)
Eating one bagel takes 1 minutes;
eating two bagels takes bagel take 2 minutes;
eating three bagels takes 4 minutes;
eating four bagels takes 8 minutes;
eating ten bagels takes 512 minutes.
Bill Gates did it. (Score:2, Informative)
Bill Gates' only published paper [berkeley.edu] gives a solution to the pancake-sorting problem. I discuss it at my blog [programmingpraxis.com].
Re: (Score:2)
Re: (Score:2)
Re: (Score:3)
The actual NP problem statement... (Score:2)
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).
Re: (Score:2)
The thing is, you're not swapping individual pancakes. You have to flip the entire stack above the insertion point. So if I have a stack [1,2,3,4,5,6,7,8,9] and I flip from where the 5 is, my stack is now [5,4,3,2,1,6,7,8,9], not [5,2,3,4,1,6,7,8,9].
That's what makes it hard. If all you were doing was swapping individual pancackes around then this would be easy, but you have to move stacks of pancakes.
Re: (Score:2)
Well, there's two problems here: calculating an optimal number of flips (which I'm not sure about) and "sorting the stack with a polynomial number of flips" which is what I think is trivial (and which the summary seemed to suggest was difficult). I was just trying to clarify that this second problem is not hard (but my post itself wasn't clear).
To further clarify, the naive algorithm for this second problem is simple and polynomial (in number of flips per pancake). Start at the bottom. If the largest panc
Re: (Score:2)
Yay! Real content on slashdot. For all programmers here we don't see algorithms often enough. Thanks.
Summary leaves out the fun part: (Score:2)
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.
Solution? (Score:4, Interesting)
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.
Re:Solution? (Score:4, Insightful)
Re: (Score:2)
Oh, I see. The problem is not that pancake flipping itself is hard, that determining the optimal pancake flipping algorithm for a stack is hard. That's believable.
Yeah... well since finding the optimal flipping solution is NP hard, you'll save time with the simple O(N^2) solution.
This just in (Score:2)
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 [wikipedia.org] 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...
Incorrect postulation? (Score:2)
Re: (Score:3)
more important question (Score:2)
The more important question is knowing when to flip the pancake.
Re: (Score:2)
Re: (Score:2)
The hard part is finding the optimal solution with the fewest number of flips.
Re: (Score:3)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3)
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.)
Re: (Score:3)
Mod parent up (Score:2)
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.