Pancake sorting
The minimum number of flips required to sort any stack of n pancakes has been shown to lie between 15/14n and 18/11n (approximately 1.07n and 1.64n), but the exact value is not known.
The upper bound was improved, thirty years later, to 18/11n by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough.
[4][5] In 2011, Laurent Bulteau, Guillaume Fertin, and Irena Rusu[6] 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.
Even though the processing power expressed by DNA flips is low, the high number of bacteria in a culture provides a large parallel computing platform.
[7] The discussion above presumes that each pancake is unique, that is, the sequence on which the prefix reversals are performed is a permutation.
However, "strings" are sequences in which a symbol can repeat, and this repetition may reduce the number of prefix reversals required to sort.
Chitturi and Sudborough (2010) and Hurkens et al. (2007) independently showed that the complexity of transforming a compatible string into another with the minimum number of prefix reversals is NP-complete.
Hurkens et al. gave an exact algorithm to sort binary and ternary strings.
Their girth: The γ(Pn) genus of Pn is:[17] Since pancake graphs have many interesting properties such as symmetric and recursive structures, small degrees and diameters compared against the size of the graph, much attention is paid to them as a model of interconnection networks for parallel computers.
