Catch up on stories from the past week (and beyond) at the Slashdot story archive

typodupeerror

## Pancake Flipping Is Hard — NP Hard260

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."
This discussion has been archived. No new comments can be posted.

## Pancake Flipping Is Hard — NP Hard

• #### I'm more interested... (Score:5, Funny)

<[bfelger] [at] [gmail.com]> on Friday November 04, 2011 @09:47AM (#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.

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

by Anonymous Coward on Friday November 04, 2011 @09:49AM (#37947604)

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

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

<peter@silma[ ].ie ['ril' in gap]> on Friday November 04, 2011 @10:05AM (#37947782) Homepage

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

on Friday November 04, 2011 @10:29AM (#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... (Score:5, Funny)

on Friday November 04, 2011 @10:34AM (#37948194) Homepage

Shhh!

You'll summon the remake!

• #### Re:Has anyone attempted to figure out... (Score:2, Funny)

on Friday November 04, 2011 @10:36AM (#37948230)

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

Mirrors should reflect a little before throwing back images. -- Jean Cocteau

Working...