Pancake Flipping is Hard

Details Pancake Flipping is Hard Pancake Flipping is Hard

2011-11-02

arxiv.org/abs/1111.0434v2

Computer Science

Computational Complexity

Corrected references

Scientific paper

Pancake Flipping is the problem of sorting a stack of pancakes of different sizes (that is, a permutation), when the only allowed operation is to insert a spatula anywhere in the stack and to flip the pancakes above it (that is, to perform a prefix reversal). In the burnt variant, one side of each pancake is marked as burnt, and it is required to finish with all pancakes having the burnt side down. Computing the optimal scenario for any stack of pancakes and determining the worst-case stack for any stack size have been challenges over more than three decades. Beyond being an intriguing combinatorial problem in itself, it also yields applications, e.g. in parallel computing and computational biology. In this paper, we show that the Pancake Flipping problem, in its original (unburnt) variant, is NP-hard, thus answering the long-standing question of its computational complexity.

Affiliated with

Also associated with

No associations

Rating

Pancake Flipping is Hard does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pancake Flipping is Hard, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pancake Flipping is Hard will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-327802