Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
November 4, 2011 03:05 pm

Pancake Flipping Is Hard — NP Hard


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

Read more of this story at Slashdot.


Original Link: http://rss.slashdot.org/~r/Slashdot/slashdot/~3/rdEtBx0SExA/pancake-flipping-is-hard-np-hard

Share this article:    Share on Facebook
View Full Article

Slashdot

Slashdot was originally created in September of 1997 by Rob "CmdrTaco" Malda. Today it is owned by Geeknet, Inc..

More About this Source Visit Slashdot