Slashdot Mirror

← Back to Stories (view on slashdot.org)

Pancake Flipping Is Hard — NP Hard

Posted by samzenpus on 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."

31 of 260 comments (clear)

  1. I'm more interested... by halivar · · Score: 4, 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.

    1. Re:I'm more interested... by Dunbal · · Score: 3, Informative

      If you used real Canadian maple syrup from real Maple trees instead of that artificial corn syrup crap the rest of the world calls "maple syrup" that tastes like dead beetles, then it really wouldn't matter if you got some on your bacon because everything tastes better with Maple Syrup.

      --
      Seven puppies were harmed during the making of this post.
    2. Re:I'm more interested... by MagicM · · Score: 4, 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.

    3. Re:I'm more interested... by fostware · · Score: 4, Funny

      Shhh!

      You'll summon the remake!

      --
      "We know what happens to people who stay in the middle of the road. They get run over." - Aneurin Bevan
    4. Re:I'm more interested... by s4ndm4n · · 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/

    5. Re:I'm more interested... by Rogue+Haggis+Landing · · 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 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.

    6. Re:I'm more interested... by djeez · · 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 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.

    7. Re:I'm more interested... by jamiesan · · Score: 2

      Beetle Juice Beetle Juice Beetle Juice

    8. Re:I'm more interested... by crakbone · · Score: 2

      I think you had "Maple flavored syrup". That was pretty common and most of the time "flavored" was off to the side or made to not stand out. As for me, pure maple syrup all the way.

    9. Re:I'm more interested... by mwvdlee · · Score: 2

      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.

      --
      Slashdot social media options: AIM, ICQ, Yahoo, Jabber and Mobile Text. Why no MySpace?
    10. Re:I'm more interested... by blair1q · · Score: 2

      That problem is Artery-hard.

  2. Has anyone attempted to figure out... by Anonymous Coward · · Score: 2, Funny

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

    1. Re:Has anyone attempted to figure out... by ComputerizedYoga · · Score: 2

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

    2. Re:Has anyone attempted to figure out... by beelsebob · · Score: 2

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

    3. Re:Has anyone attempted to figure out... by EuclideanSilence · · Score: 2

      The above is a solution to the question "how can I flip sort a stack of pancakes in polynomial time?"

      The question to be answered is: "let R(stack) be the minimum number of flips to sort a given stack. Let F(N) be the maximum value of R(stack) for all stacks of size N. Compute F(N)."

      Or, more precisely since it is a decision problem, probably something like "can all stacks of size N be flip-sorted in less than F(N) flips?", but it's trivially polytime equivalent.

      These french mathematicians showed that if you can compute F(N) then you can compute any NP problem in polytime. It does not however show that a solution to P=NP solves the pancake flipping problem.

      The article an summary were not very exact in their wording.

  3. Towers of Hanoi? by Tynin · · Score: 2

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

    1. Re:Towers of Hanoi? by AxeMurder · · Score: 2

      Not exactly, in the towers game you have 3 stacks and you rearrange the pieces by removing the top of a stack and placing it on the top of another stack. The challenge comes from the following rule: a bigger piece can never be placed above a smaller piece.

    2. Re:Towers of Hanoi? by yakatz · · Score: 3, Informative

      The difference is in where you flip. In the Towers of Hanoi, you do not flip the whole stack, you can only move the pieces one at a time between poles.
      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

  4. very friendly np-hard problem by Anonymous Coward · · 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? :)

  5. Getting there slowly.. by RenHoek · · Score: 2

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

  6. Bill Gates did it. by Anonymous Coward · · Score: 2, Informative

    Bill Gates' only published paper gives a solution to the pancake-sorting problem. I discuss it at my blog.

    1. Re:Bill Gates did it. by orgelspieler · · Score: 2

      Great, now I have to reboot my skillet any time I want to change the temperature setting, and there are viruses in my batter.

  7. Re:I now understand by frisket · · 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...

  8. Solution? by Erich · · Score: 3, Interesting
    I had something like this was an interview question once. My solution:

    Assume we are stacking pancakes with largest at the bottom.

    1. Find the largest unsorted pancake
    2. Flip that to the top
    3. Flip from the bottom-most unsorted pancake. (One additional pancake is now sorted)
    4. Repeat until sorted

    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.

    --

    -- Erich

    Slashdot reader since 1997

    1. Re:Solution? by Erich · · Score: 3, Insightful

      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.

      --

      -- Erich

      Slashdot reader since 1997

  9. Incorrect postulation? by fey000 · · Score: 2

    There seems to be a miscommunication here. You can prove that P = NP only if you can solve an NP-complete problem in polynomial time (or some other type that can be reduced to every other problem in the set). The article refers to NP-hard, which is not necessarily in the NPC set. Thus, solving the pancakes problem in polynomial time only guarantees that P = NP for the pancake problem (again, unless you can reduce it to every other problem).

    1. Re:Incorrect postulation? by canajin56 · · Score: 2

      NP-Hard means it can be used to solve any NP-Complete problem. Not the opposite of that, like you seem to think...

      --
      ASCII stupid question, get a stupid ANSI
  10. Re:Since it comes from French scientists... by godrik · · Score: 2

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

  11. Comment removed by account_deleted · · Score: 2

    Comment removed based on user account deletion

  12. Re:I now understand by Dunbal · · Score: 2

    long for a good waffle.

    Heresy! BURN THE UNBELIEVER!

    --
    Seven puppies were harmed during the making of this post.
  13. Re:Since it comes from French scientists... by Schmorgluck · · Score: 2

    And butter. How could I forget butter? I'm losing a lot of Breton creds on this one...

    --
    There's nothing like $HOME