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

 



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

×
Math

+ - Pancake flipping is hard - NP hard->

Submitted by mikejuk
mikejuk (1801200) 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.
Pancakes have never seemed so interesting...."

Link to Original Source
This discussion was created for logged-in users only, but now has been archived. No new comments can be posted.

Pancake flipping is hard - NP hard

Comments Filter:

No problem is so large it can't be fit in somewhere.

Working...