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:
“I tell you, sir, the only safeguard of order and discipline in the modern world is a standardized worker with interchangeable parts. That would solve the entire problem of management.”
—Jean Giraudoux (1882–1944)
“it was older sure than this year’s cutting,
Or even last year’s or the year’s before.
The wood was gray and the bark warping off it
And the pile somewhat sunken. Clematis
Had wound strings round and round it like a bundle.”
—Robert Frost (1874–1963)