Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror

Slashdot videos: Now with more Slashdot!

  • View

  • Discuss

  • Share

We've improved Slashdot's video section; now you can view our video interviews, product close-ups and site visits with all the usual Slashdot options to comment, share, etc. No more walled garden! It's a work in progress -- we hope you'll check it out (Learn more about the recent updates).

×
Image

Pancake Flipping Is Hard — NP Hard 260

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

Pancake Flipping Is Hard — NP Hard

Comments Filter:
  • Solution? (Score:4, Interesting)

    by Erich (151) on Friday November 04, 2011 @11:09AM (#37947832) Homepage Journal
    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.

"A car is just a big purse on wheels." -- Johanna Reynolds

Working...