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

 



Forgot your password?
typodupeerror
Slashdot Deals: Prep for the CompTIA A+ certification exam. Save 95% on the CompTIA IT Certification Bundle ×
Image

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

Pancake Flipping Is Hard — NP Hard

Comments Filter:

Related Links Top of the: day, week, month.

The confusion of a staff member is measured by the length of his memos. -- New York Times, Jan. 20, 1981

Working...