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:
“From cradle to grave this problem of running order through chaos, direction through space, discipline through freedom, unity through multiplicity, has always been, and must always be, the task of education, as it is the moral of religion, philosophy, science, art, politics and economy; but a boy’s will is his life, and he dies when it is broken, as the colt dies in harness, taking a new nature in becoming tame.”
—Henry Brooks Adams (1838–1918)
“How have you left the ancient love
That bards of old enjoyed in you!
The languid strings do scarcely move!
The sound is forced, the notes are few!”
—William Blake (1757–1827)