# Pancake Flipping Is Hard — NP Hard

#### samzenpus posted more than 2 years ago | from the sorting-a-large-stack dept.

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... (4, Funny)

## halivar (535827) | more than 2 years ago | (#37947590)

...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:I'm more interested... (0)

## Anonymous Coward | more than 2 years ago | (#37947792)

It's good on sausage too!

## Re:I'm more interested... (1)

## kungfugleek (1314949) | more than 2 years ago | (#37947896)

## Re:I'm more interested... (1)

## Tarlus (1000874) | more than 2 years ago | (#37947970)

My day can now start on a happy note. Thanks for that. :)

## Re:I'm more interested... (3, Informative)

## Dunbal (464142) | more than 2 years ago | (#37947976)

## Re:I'm more interested... (1)

## X0563511 (793323) | more than 2 years ago | (#37948028)

Those are some tasty beetles.

## Re:I'm more interested... (1)

## operagost (62405) | more than 2 years ago | (#37948088)

## Re:I'm more interested... (1)

## Dunbal (464142) | more than 2 years ago | (#37948244)

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 overseas.

## Re:I'm more interested... (-1)

## Anonymous Coward | more than 2 years ago | (#37948510)

## Re:I'm more interested... (1)

## kimvette (919543) | more than 2 years ago | (#37948260)

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:I'm more interested... (1)

## Golddess (1361003) | more than 2 years ago | (#37948446)

syrupin place of the standard, dull, white sugar in certain recipes. So there's actually a maplesugaryou say? Wonder how it'd compare...## Re:I'm more interested... (2)

## s4ndm4n (1361751) | more than 2 years ago | (#37948562)

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:I'm more interested... (4, Funny)

## MagicM (85041) | more than 2 years ago | (#37948118)

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... (0)

## Anonymous Coward | more than 2 years ago | (#37948172)

## Re:I'm more interested... (4, Funny)

## fostware (551290) | more than 2 years ago | (#37948194)

Shhh!

You'll summon the remake!

## Re:I'm more interested... (1)

## Scaba (183684) | more than 2 years ago | (#37948324)

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:I'm more interested... (0)

## Anonymous Coward | more than 2 years ago | (#37948648)

Yes of course, which is why i do it.

## Re:I'm more interested... (1)

## Crudely_Indecent (739699) | more than 2 years ago | (#37948336)

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... (5, Informative)

## Rogue Haggis Landing (1230830) | more than 2 years ago | (#37948612)

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

reallyhardcore 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:I'm more interested... (2)

## djeez (472062) | more than 2 years ago | (#37948628)

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 yeah, I consume about two gallons of maple syrup per year plus maple butter on toasts and maple sugar instead of brown sugar and I actually keep a bottle of syrup at work to sweeten my (and my coworker's) coffee.

Everything is better with maple.

## Re:I'm more interested... (1)

## Synerg1y (2169962) | more than 2 years ago | (#37948492)

Reminds me of the coffee apparatus from the lab in breaking bad tv series :)

## nerds (-1)

## Anonymous Coward | more than 2 years ago | (#37947600)

Nerds!

## Re:nerds (1)

## AnujMore (2009920) | more than 2 years ago | (#37947744)

## Re:nerds (1)

## Dunbal (464142) | more than 2 years ago | (#37948000)

## Re:nerds (1)

## need4mospd (1146215) | more than 2 years ago | (#37948294)

## Re:nerds (1)

## Dunbal (464142) | more than 2 years ago | (#37948306)

## Re:nerds (0)

## Anonymous Coward | more than 2 years ago | (#37948130)

You must be new here

## Has anyone attempted to figure out... (2, Funny)

## Anonymous Coward | more than 2 years ago | (#37947604)

How we can do it in polynomial time but computers can't?

## Re:Has anyone attempted to figure out... (1)

## halivar (535827) | more than 2 years ago | (#37947674)

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:Has anyone attempted to figure out... (0)

## Anonymous Coward | more than 2 years ago | (#37947714)

You can do it in polynomial time if you overclock your computer exponentially in n.

## Re:Has anyone attempted to figure out... (1)

## durrr (1316311) | more than 2 years ago | (#37947762)

## Re:Has anyone attempted to figure out... (0)

## Anonymous Coward | more than 2 years ago | (#37948026)

To prove that an algorithm runs in polynomial time, it's not enough to time it for n=1..10 -- you have to publish the algorithm and a run-time analysis. If you solve the problem with your brain, the published algorithm would be a map of your brain's neurons and a biochemical simulator. The referees would rather read C++.

## Re:Has anyone attempted to figure out... (1)

## Joce640k (829181) | more than 2 years ago | (#37947902)

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:Has anyone attempted to figure out... (1)

## Joce640k (829181) | more than 2 years ago | (#37948036)

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:Has anyone attempted to figure out... (1)

## IkeTo (27776) | more than 2 years ago | (#37948040)

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:Has anyone attempted to figure out... (0)

## Anonymous Coward | more than 2 years ago | (#37948164)

Yes, the problem is not to sort a stack of pancakes, but to determine f(n), the minimum number of flips for all possible pancake stacks of size n. Determining f(n) is NP-hard in n.

## Re:Has anyone attempted to figure out... (1)

## Elros (735454) | more than 2 years ago | (#37948046)

You've got 2n flips, but you haven't accounted for determining the location of the next pancake. Granted, I still think that can be done in n^2 time.

## Re:Has anyone attempted to figure out... (1)

## ebh (116526) | more than 2 years ago | (#37948554)

Right. 2n flips, 2^n compares. Unless we keep using the word "touch", but they do not think it means what we think it means.

I'm presuming that whatever process we use to determine the next pancake to flip to the top doesn't count as "touching" it, only the flip does. Is that wrong?

## Re:Has anyone attempted to figure out... (1)

## ebh (116526) | more than 2 years ago | (#37948572)

s/2^n/n^2/

## Re:Has anyone attempted to figure out... (0)

## Anonymous Coward | more than 2 years ago | (#37948068)

Number of compares, not number of flips, Locate the next pancake is where your algorithm needs to be efficient, and a 2n claim would mean only 2n compares would only give you 10 compares to sort 5 pancakes.

## Re:Has anyone attempted to figure out... (0)

## Anonymous Coward | more than 2 years ago | (#37948328)

RTFA. The 3rd paragraph of the linked article explains what you're missing (and why you're wrong):

The only restriction, and this is what makes it difficult, is that you can't touch them with anything but your spatula. All you can do is insert your spatula at a division point and flip the entire set of pancakes you have picked up upside down in one operation.

## Re:Has anyone attempted to figure out... (0)

## Anonymous Coward | more than 2 years ago | (#37947746)

If you can prove that you can do it in polynomial time, then there is a million bucks waiting for you in the bank. Also fame and glory: http://en.wikipedia.org/wiki/Millennium_Prize_Problems#P_versus_NP

## Re:Has anyone attempted to figure out... (1)

## ledow (319597) | more than 2 years ago | (#37947778)

"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. But when you get to 1,000,000 cards it's going to beat me. And when I get to 1,000,000,000 cards, I'll die before it even gets bored doing it. But that's not an answer.

The point is to find a way that tasks that currently take "size of problem to some power" time to complete can be done in significantly less than that (i.e. no powers, or even log time!) no matter how big the problem is scaled up to.

Humans lose at an awful lot of computational problems but only when they are scaled up. It's the scaling that concerns P=NP and the question itself is basically "can we STOP things that do that scaling faster than we could ever hope to catch up?" It's a way to do things that require n^26 operations to only need n, or log n, or some other non-polynomial time. The n itself doesn't matter one jot because that's only a SINGLE example of a particular type of that problem. If we crack how to remove those powers from the time taken, then any number of n won't really matter at all. But if we leave the powers try and try an n greater than a few dozen, we rapidly run into extreme amounts of trouble.

How do you stop a problem needing FOUR times the computing power just because you DOUBLED the size of the input? That's basically what P=NP solution finders are trying to answer.

## Re:Has anyone attempted to figure out... (2)

## ComputerizedYoga (466024) | more than 2 years ago | (#37948240)

"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 size of the input squares the computation involved. So like ... no known general solution to SAT [wikipedia.org] is better than 2^n.

So what that means is going from input size = 10 to input size = 20 would require a million times more power, and input size = 20 to input size = 21 would require twice the power that it would take to do input size = 20. This is WAY worse than n^x (where x is a constant).

## Re:Has anyone attempted to figure out... (1)

## nschubach (922175) | more than 2 years ago | (#37948320)

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:Has anyone attempted to figure out... (1)

## beelsebob (529313) | more than 2 years ago | (#37947926)

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, what is it?

## Re:Has anyone attempted to figure out... (0)

## Anonymous Coward | more than 2 years ago | (#37948158)

More like O(n) actually (2 * number of pancakes)

As pointed by Joce640k a few posts above.

I would also be interested to know what we're all missing.

## Re:Has anyone attempted to figure out... (2)

## beelsebob (529313) | more than 2 years ago | (#37948410)

it still takes O(n) time to select the pancake to flip.

## Re:Has anyone attempted to figure out... (1)

## AlecC (512609) | more than 2 years ago | (#37948358)

And O(n^2) is polynomial - it has a ^2 in it. And, apparently, they have proved there is no shortcut which is not polynomial unless P=NP. They have shown that this is one of a class of problems for which time to solve increases fast enough that for some value of n it must become uncomputable.

## Re:Has anyone attempted to figure out... (1)

## beelsebob (529313) | more than 2 years ago | (#37948452)

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 problems have O(k * n^1) complexity, etc. Polynomial solutions is exactly what we want.

## Re:Has anyone attempted to figure out... (1)

## ComputerizedYoga (466024) | more than 2 years ago | (#37948432)

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

optimalsorting is apparently what's hard.## Re:Has anyone attempted to figure out... (1)

## Dunbal (464142) | more than 2 years ago | (#37948022)

## Re:Has anyone attempted to figure out... (1)

## Opportunist (166417) | more than 2 years ago | (#37948114)

Is that, like, you know how to stroke it but it's kinda hard to tell your girlfriend how to do it right?

## Re:Has anyone attempted to figure out... (1)

## Dunbal (464142) | more than 2 years ago | (#37948280)

## Re:Has anyone attempted to figure out... (1, Funny)

## jank1887 (815982) | more than 2 years ago | (#37948230)

computers have a specific disadvantage with this problem. they have trouble holding the spatula.

## Re:Has anyone attempted to figure out... (1)

## Hatta (162192) | more than 2 years ago | (#37948256)

You can't.

## Towers of Hanoi? (2)

## Tynin (634655) | more than 2 years ago | (#37947650)

## Re:Towers of Hanoi? (2)

## AxeMurder (1795476) | more than 2 years ago | (#37947780)

## Re:Towers of Hanoi? (1)

## Opportunist (166417) | more than 2 years ago | (#37948136)

Erh... like in the Towers of Hanoi [wikipedia.org] problem?

## Re:Towers of Hanoi? (1)

## nschubach (922175) | more than 2 years ago | (#37948376)

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:Towers of Hanoi? (1)

## Zaphod The 42nd (1205578) | more than 2 years ago | (#37947812)

## Re:Towers of Hanoi? (1)

## AnujMore (2009920) | more than 2 years ago | (#37947814)

Here's a link for you to read what Towers of Hanoi exactly are. https://secure.wikimedia.org/wikipedia/en/wiki/Tower_of_Hanoi [wikimedia.org]

Towers of Hanoi aims at moving a set of discs in the same order from one peg to another, and this one's just talking about sorting.

## Re:Towers of Hanoi? (3, Informative)

## yakatz (1176317) | more than 2 years ago | (#37947820)

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:Towers of Hanoi? (1)

## Carewolf (581105) | more than 2 years ago | (#37947824)

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:Towers of Hanoi? (1)

## Carewolf (581105) | more than 2 years ago | (#37947840)

Hmm. This actually means that if you prove this is a reworded version of the Towers of Hanoi, you would have proven N != NP.

## Re:Towers of Hanoi? (0)

## Anonymous Coward | more than 2 years ago | (#37947836)

Sounds like they just reworded the Towers of Hanoi puzzle, which has been around for a long time.

Hanoi is 3 towers, move 1 disc at a time, not allowed to put a large disc on a small one. Optimal solution is well-known.

Pancakes is 1 stack, flip as many as you want at a time, no restrictions on intermediate steps. Not so sure about optimal solution.

## Re:Towers of Hanoi? (1)

## ShogunTux (1236014) | more than 2 years ago | (#37948412)

The most optimal one for years has been the one that Bill Gates [npr.org] devised, which would result in 5/3 N number of flips, but now the best solution is only 1% more optimal than his solution.

And funnily, that's really the only known contribution that Bill Gates has done to the field of computer science, well, and a tad bit of programming in Windows 1.0 and the editions of DOS that came before that. After that, he didn't do anything anymore, or at least acknowledge that he did, since he became more occupied with managing Microsoft than coding.

## Re:Towers of Hanoi? (0)

## Anonymous Coward | more than 2 years ago | (#37948268)

Reversing a prefix of more than one element in ToH would violate the rules of ToH. Pieces can only be placed on larger pieces, so flipping a stack would place larger pieces on smaller pieces.

## I now understand (1)

## EmperorOfCanada (1332175) | more than 2 years ago | (#37947666)

## Re:I now understand (5, Funny)

## frisket (149522) | more than 2 years ago | (#37947782)

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:I now understand (1)

## Dunbal (464142) | more than 2 years ago | (#37948080)

## Re:I now understand (1)

## davidbrit2 (775091) | more than 2 years ago | (#37948652)

## Re:I now understand (1)

## Zaphod The 42nd (1205578) | more than 2 years ago | (#37947852)

What exactly do you understand now that you didn't before?

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.

## very friendly np-hard problem (2, Informative)

## Anonymous Coward | more than 2 years ago | (#37947676)

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.. (2)

## RenHoek (101570) | more than 2 years ago | (#37947686)

Now if they can only explain to me what the hell 'polynomial time' is.. maybe with a bagel allegory..

## Re:Getting there slowly.. (1)

## Anonymous Coward | more than 2 years ago | (#37947816)

I believe that eating bagels happens in polynomial time.

The first bagel goes down easily.

The second bagel takes a little longer than the first.

The third bagel takes even longer than the second.

The fourth bagel takes a lot longer than the third.

Each subsequent bagel will take a lot longer than the previous one.

## Re:Getting there slowly.. (1)

## Dunbal (464142) | more than 2 years ago | (#37948116)

## Re:Getting there slowly.. (1)

## JonySuede (1908576) | more than 2 years ago | (#37948304)

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 bagels takes 277.75 minutes.

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 10 minutes;

eating four bagels takes 21.25 minutes;

eating ten bagels takes 512 minutes.

## Re:Getting there slowly.. (1)

## fuzzfuzz (881119) | more than 2 years ago | (#37947868)

## Bill Gates did it. (2, Informative)

## Anonymous Coward | more than 2 years ago | (#37947704)

Bill Gates' only published paper [berkeley.edu] gives a solution to the pancake-sorting problem. I discuss it at my blog [programmingpraxis.com] .

## Since it comes from French scientists... (0)

## Anonymous Coward | more than 2 years ago | (#37947760)

Shouldn't it be crepe flipping?

## Re:Since it comes from French scientists... (1)

## Dunbal (464142) | more than 2 years ago | (#37948142)

## Let's get this out of the way, OK? (0)

## Anonymous Coward | more than 2 years ago | (#37947776)

We already know P = NP when N = 1 and P = 0.

OK. Now we can discuss the article.

## The actual NP problem statement... (1)

## JMZero (449047) | more than 2 years ago | (#37947794)

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:The actual NP problem statement... (1)

## Millennium (2451) | more than 2 years ago | (#37947892)

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:The actual NP problem statement... (1)

## JMZero (449047) | more than 2 years ago | (#37948156)

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 pancake is not on the bottom, flip the stack starting at the largest pancake (so that the largest pancake is at the top). Now flip the whole stack. Now imagine the bottom pancake is part of the table and repeat the process. You'll flip at most twice for each pancake.

## Re:The actual NP problem statement... (0)

## Anonymous Coward | more than 2 years ago | (#37948532)

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.

It isn't as hard as you think, watch:

[5,4,3,2,1,6,7,8,9] - To speed this up, I'm going to ignore the ones that are already in the right place (6,7,8,9) [M=5]

[>5<,4,3,2,1,6,7,8,9] - Search to find the biggest in the unsorted section (N=1)

[>5<,4,3,2,1,6,7,8,9] - Flip 1->N so that pancake N is now on the top (This is an identity operation since N is 1 so is already the top)

[1,2,3,4,>5<,6,7,8,9] - Flip 1->M so that the top pancake is now at the bottom of the unsorted section that makes up the top of the stack

[1,2,3,>4<,5,6,7,8,9] - Find the biggest (N=4) [M=4]

[>4<,3,2,1,5,6,7,8,9] - Flip 1->N

[1,2,3,>4<,5,6,7,8,9] - Flip 1->M

Rinse, repeat

[1,2,3,4,5,6,7,8,9] - Done [N=0,M=1]

You can improve the efficiency by skipping to the next iteration when N=M after the find biggest stage but the worst case efficiency of this approach isn't particularly good (O(n**2) I think) but is both polynomial and reasonably simple. (The paper in question is apparently discussing calculating the minimum number of flips that are absolutely necessary which IS a much harder problem)

## can we trust this story? (0)

## Anonymous Coward | more than 2 years ago | (#37947822)

any reason to think this isn't just another bogus complexity paper on the arxiv? has anyone credible verified this?

## Summary leaves out the fun part: (1)

## DogFacedJo (949100) | more than 2 years ago | (#37947830)

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? (3, Interesting)

## Erich (151) | more than 2 years ago | (#37947832)

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? (3, Insightful)

## Erich (151) | more than 2 years ago | (#37947866)

## Re:Solution? (0)

## Anonymous Coward | more than 2 years ago | (#37948090)

The problem is your solution is not always optimal. The pancake flipping problem considers

optimalsolutions.## Important Distinction (1)

## Anonymous Coward | more than 2 years ago | (#37947834)

It's worth noting that sorting the pancakes in polynomial time is easy.

From wikipedia [wikipedia.org] : "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

optimalsequence of flips in polynomial time for any given stack of pancakes that's NP-Hard.## This just in (1)

## Zaphod The 42nd (1205578) | more than 2 years ago | (#37947888)

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...

Cool story bro.

## Re:This just in (0)

## Anonymous Coward | more than 2 years ago | (#37948558)

Not the mention the obnoxious amount of space reversed for ads

## Simple algorithm (0)

## Anonymous Coward | more than 2 years ago | (#37947948)

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?

## Incorrect postulation? (2)

## fey000 (1374173) | more than 2 years ago | (#37948004)

## You burned it! (0)

## Anonymous Coward | more than 2 years ago | (#37948128)

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.

## Flipping pancakes? PAH, away with you. (0)

## Anonymous Coward | more than 2 years ago | (#37948210)

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.

## more important question (1)

## tverbeek (457094) | more than 2 years ago | (#37948396)

The more important question is knowing

whento flip the pancake.