Editing Pancake sorting (section)

===The original pancake problem===
The minimum number of flips required to sort any stack of {{math|''n''}} pancakes has been shown to lie between {{math|{{sfrac|15|14}}''n''}} and {{math|{{sfrac|18|11}}''n''}} (approximately 1.07''n'' and 1.64''n''), but the exact value is not known.<ref>{{Cite book|last1=Fertin|first1=G.|last2=Labarre|first2=A.|last3=Rusu|first3=I.|last4=Tannier|first4=E.|last5=Vialette|first5=S. |title=Combinatorics of Genome Rearrangements|publisher= The MIT Press|year= 2009|isbn=9780262062824}}</ref>

The simplest pancake sorting algorithm performs at most {{math|2''n'' &minus; 3}} flips. In this algorithm, a kind of [[selection sort]], we bring the largest pancake not yet sorted to the top with one flip; take it down to its final position with one more flip; and repeat this process for the remaining pancakes.

In 1979, [[Bill Gates]] and [[Christos Papadimitriou]]<ref name=Gates1979/> gave a lower bound of {{math|{{sfrac|17|16}}''n''}} (approximately 1.06''n'') flips and an upper bound of {{math|{{sfrac|(5''n''+5)|3}}}}. The upper bound was improved, thirty years later, to  {{math|{{sfrac|18|11}}''n''}} by a team of researchers at the [[University of Texas at Dallas]], led by Founders Professor [[Hal Sudborough]].<ref name="Sudborough">{{cite web|title=Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics|publisher=University of Texas at Dallas News Center|date=September 17, 2008|url=http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen|access-date=November 10, 2008|quote=A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established.|archive-url=https://web.archive.org/web/20120214070902/http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen|archive-date=February 14, 2012|url-status=dead}}</ref><ref>{{Cite journal|last1=Chitturi|first1=B.|last2=Fahle|first2=W.|last3=Meng|first3=Z.|last4=Morales|first4=L.|last5=Shields|first5=C. O.|last6=Sudborough|first6=I. H.|last7=Voit|first7=W.|date=2009-08-31|title=An (18/11)n upper bound for sorting by prefix reversals|journal=Theoretical Computer Science|series=Graphs, Games and Computation: Dedicated to Professor Burkhard Monien on the Occasion of his 65th Birthday|volume=410|issue=36|pages=3372–3390|doi=10.1016/j.tcs.2008.04.045|doi-access=free}}</ref>

In 2011, Laurent Bulteau, Guillaume Fertin, and Irena Rusu<ref>{{Cite journal|journal=Journal of Computer and System Sciences|doi=10.1016/j.jcss.2015.02.003|title=Pancake Flipping Is Hard|last1=Bulteau|first1=Laurent|last2=Fertin|first2=Guillaume|last3=Rusu|first3=Irena|volume=81|number=8|pages=1556–1574|arxiv=1111.0434|year=2015}}</ref> proved that the problem of finding the shortest sequence of flips for a given stack of pancakes is [[NP-hard]], thereby answering a question that had been open for over three decades.