Pancake Flipping is Hard

• Published in 2011
• Added on 2013-11-15

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.

Links

• http://arxiv.org/abs/1111.0434
• http://arxiv.org/pdf/1111.0434v2

Other information

BibTeX entry

@article{Bulteau2011,
	key = {Bulteau2011},
	type = {article},
	title = {Pancake Flipping is Hard},
	author = {Bulteau, Laurent and Fertin, Guillaume and Rusu, Irena},
	abstract = {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.},
	comment = {},
	date_added = {2013-11-15},
	date_published = {2011-11-01},
	urls = {http://arxiv.org/abs/1111.0434,http://arxiv.org/pdf/1111.0434v2},
	collections = {Attention-grabbing titles,Puzzles,Basically computer science,Easily explained,Food},
	month = {nov},
	url = {http://arxiv.org/abs/1111.0434 http://arxiv.org/pdf/1111.0434v2},
	year = 2011,
	archivePrefix = {arXiv},
	eprint = {1111.0434},
	primaryClass = {cs.CC},
	urldate = {2013-11-15}
}