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."
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? :)
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: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:I'm more interested... (Score:4, Informative)
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.