Pancake flipping is hard

DOI10.1007/978-3-642-32589-2_24zbMATH Open1328.68084DBLPjournals/jcss/BulteauFR15arXiv1111.0434OpenAlexW1846975517WikidataQ56287379 ScholiaQ56287379MaRDI QIDQ494050FDOQ494050

Authors: Laurent Bulteau, Guillaume Fertin, Irena Rusu 

Publication date: 31 August 2015

Published in: Journal of Computer and System Sciences, Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1111.0434

Recommendations

• Pancake flipping is hard
• On the problem of sorting burnt pancakes
• Pancake flipping and sorting permutations
• On average and highest number of flips in pancake sorting
• Polynomial-time sortable stacks of burnt pancakes

zbMATH Keywords

permutationscomputational complexitypancake problemprefix reversals

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• A group-theoretic model for symmetric interconnection networks
• Bounds for sorting by prefix reversal
• On the Diameter of the Pancake Network
• Pancake flipping is hard
• On average and highest number of flips in pancake sorting
• Transforming cabbage into turnip
• On the problem of sorting burnt pancakes
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Title not available (Why is that?)
• Title not available (Why is that?)
• Genome Rearrangements and Sorting by Reversals
• Algorithms – ESA 2005
• Polynomial-time sortable stacks of burnt pancakes

Cited In (32)

• Title not available (Why is that?)
• Upper bounds for sorting permutations with a transposition tree
• Some relations on prefix reversal generators of the symmetric and hyperoctahedral group
• Sorting permutations and binary strings by length-weighted rearrangements
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Sorting by prefix block-interchanges
• Cycles in the burnt pancake graph
• The spectral gap of graphs arising from substring reversals
• Shortest reconfiguration of perfect matchings via alternating cycles
• Greedy flipping of pancakes and burnt pancakes
• An audit tool for genome rearrangement algorithms
• Pancake flipping is hard
• On average and highest number of flips in pancake sorting
• On the problem of sorting burnt pancakes
• Prefix and suffix reversals on strings
• Successor rules for flipping pancakes and burnt pancakes
• Relative-order abstractions for the pancake problem
• Physical zero-knowledge proof protocol for Topswops
• Prefix and Suffix Reversals on Strings
• On the complexity of the pancake problem
• Sorting by prefix reversals and prefix transpositions
• The mathematics of burger flipping
• Sorting genomes by prefix double-cut-and-joins
• Groupoid Action and Rearrangement Problem of Bicolor Arrays by Prefix Reversals
• (Prefix) reversal distance for (signed) strings with few blocks or small alphabets
• Pancake flipping and sorting permutations
• Polynomial-time sortable stacks of burnt pancakes
• Approximation algorithms for sorting by length-weighted prefix and suffix operations
• How to sort by walking and swapping on paths and trees
• Dynamically improved bounds bidirectional search
• Token Swapping on Trees
• On the complexity of the pancake problem

This page was built for publication: Pancake flipping is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q494050)