Pancake flipping is hard - NP hard

### New Book Reviews!

 Pancake flipping is hard - NP hard
Written by Mike James
Thursday, 03 November 2011

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.

Pancake flipping is a long-standing algorithmic problem.

You start with a stack of pancakes of different sizes and your task is to sort them into order. The only restriction, and this is what makes it difficult, is that you can't touch them with anything but your spatula. All you can do is insert your spatula at a division point and flip the entire set of pancakes you have picked up upside down in one operation.

There is a variant on the problem where you have burned all the pancakes on one side and you have to finish the sort with all the burned sides face down.

The question to be answered in both cases is, if the stack has n pancakes, what is the maximum number of flips needed as a function of n, i.e. f(n)?

In short, what is the computational complexity of the pancake problem?

At the moment  we only know f(n) for n<=19 (for the burnt version of the problem we only know it for n<=17). Apart from this we know a few general upper and lower  bounds but these aren't thought to be particularly tight.

Now a team of three computer scientists from Laboratoire d'Informatique de Nantes-Atlantique have succeeded in proving that the pancake problem is NP hard. Roughly stated, this makes the problem at least as hard as the hardest in the NP class. What this means is that if you can find a polynomial time solution to the pancake problem then you have proved that P=NP.

The paper doesn't improve the bounds on the complexity function, but it has managed to show that proving that a known lower bound - the number of breakpoints - is a tight lower bound, is also NP hard.

The algorithm does have some practical purposes - in comparative genomics for example, and there is an even more useful related problem of sorting by reversal.

But who needs practical applications to be interested in pancakes?

#### More Information

Pancake Flipping is Hard arXiv:1111.0434v1

#### Related articles on I Programmer

Computational Complexity

Computability

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Twitter or Facebook or sign up for our weekly newsletter

 //No Comment - I Would Not Plant Apple Trees, Crowds Should Talk More & Twitter Election Rumors 07/03/2017• I Would Not Plant Apple Trees If the World Will Be Wiped: Analyzing Hundreds of Millions of Behavioral Records of Players During an MMORPG Beta Test • Deliberation increases the wisdom of crowd [ ... ] + Full Story Microsoft Edge Falls Victim At Pwn2Own 22/03/2017This year's 10th anniversary Pwn2Own spanned over thee days rather than the previous two and was won by the team from 360 Security who achieved a full virtual machine escape through Microsoft Edge. + Full Story More News

Last Updated ( Thursday, 03 November 2011 )

 RSS feed of news items only Copyright © 2017 i-programmer.info. All Rights Reserved. Joomla! is Free Software released under the GNU/GPL License.