  Pancake flipping, a famous open problem in computer science, can be
formalised as the problem of sorting a permutation of positive integers using
as few prefix reversals as possible. In that context, a prefix reversal of
length k reverses the order of the first k elements of the permutation. The
burnt variant of pancake flipping involves permutations of signed integers, and
reversals in that case not only reverse the order of elements but also invert
their signs. Although three decades have now passed since the first works on
these problems, neither their computational complexity nor the maximal number
of prefix reversals needed to sort a permutation is yet known. In this work, we
prove a new lower bound for sorting burnt pancakes, and show that an important
class of permutations, known as "simple permutations", can be optimally sorted
in polynomial time.
