Unread 11-04-2011, 05:14 PM
sl4shd0t
Posts: n/a
  #1  
Default Pancake Flipping Is Hard — NP Hard

</img>
</img>
mikejuk writes "French computer scientists have finally proved that sorting pancakes is hard &mdash; NP hard. No really &mdash; 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 &mdash; 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.
[IMG]http://feeds.feedburner.com/~r/Slashdot/slashdotDevelopers/~4/rdEtBx0***A[/IMG]

More...
Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT. The time now is 06:03 PM.


Powered by vBulletin® Version 3.0.1
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.