Pancake Flipping Is Hard — NP Hard 260
Posted
by
samzenpus
from the sorting-a-large-stack dept.
from the sorting-a-large-stack dept.
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.
Has anyone attempted to figure out... (Score:2, Funny)
How we can do it in polynomial time but computers can't?
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: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:Has anyone attempted to figure out... (Score:2, Funny)
computers have a specific disadvantage with this problem. they have trouble holding the spatula.