Editing Pancake sorting (section)

==The pancake problem on strings==
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]]. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. Chitturi<ref name=":0">{{cite journal|journal=Discrete Mathematics, Algorithms and Applications|volume= 03| issue = 3|pages=269–286|doi=10.1142/S1793830911001206|year=2011|last1=Chitturi|first1=Bhadrachalam|title=A Note on Complexity of Genetic Mutations }}</ref>  (2011) proved that the complexity of transforming a compatible signed string into another with the minimum number of signed prefix reversals—the burnt pancake problem on strings—is NP-complete.