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:
“How much atonement is enough? The bombing must be allowed as at least part-payment: those of our young people who are concerned about the moral problem posed by the Allied air offensive should at least consider the moral problem that would have been posed if the German civilian population had not suffered at all.”
—Clive James (b. 1939)
“When my lover came to bed,
the knot came untied
all by itself.
My dress,
held up by the strings of a loosened belt,
barely stayed on my hips.
Friend,
that’s as much as I know now.
When he touched my body,
I couldn’t at all remember
who he was,
who I was,
or how It was.”
—Amaru (c. seventh century A.D.)