The Pancake Problem On Strings
The above discussion presumes that each pancake is unique, i.e. no two of them are identical. Hence the sequence on which the prefix reversals are performed is a "permutation", i.e. the sequence in which every symbol occurs exactly once. However, "strings" are sequences in which a symbol can repeat. Chitturi and Sudborough (2010) and Hurkens et al. (2007) independently showed that the complexity of transforming a compatible string into another with 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 (2011) proved that the complexity of transforming a compatible signed string into another with prefix reversals, i.e. the burnt pancake problem on strings, is NP-complete.
Read more about this topic: Pancake Sorting
Famous quotes containing the words problem and/or strings:
“The problem ... is emblematic of what hasn’t changed during the equal opportunity revolution of the last 20 years. Doors opened; opportunities evolved. Law, institutions, corporations moved forward. But many minds did not.”
—Anna Quindlen (b. 1952)
“A culture may be conceived as a network of beliefs and purposes in which any string in the net pulls and is pulled by the others, thus perpetually changing the configuration of the whole. If the cultural element called morals takes on a new shape, we must ask what other strings have pulled it out of line. It cannot be one solitary string, nor even the strings nearby, for the network is three-dimensional at least.”
—Jacques Barzun (b. 1907)