A quadratic lower bound for Topswops

作者：Morales Linda; Sudborough Hal^*

来源：Theoretical Computer Science, 2010, 411(44-46): 3965-3970.

DOI：10.1016/j.tcs.2010.08.011

• Topswops
• Reverse card shuffle
• Pancake problem
• Prefix reversals
• Lower bounds
• Permutations
• Conway card games

A quadratic lower bound for the topswops function is exhibited. This provides a non-trivial lower bound for a problem posed by J.H. Conway, D.E. Knuth, M. Gardner and others. We describe an infinite family of permutations, each taking a linear number of steps for the topswops process to terminate, and a chaining process that creates from them an infinite family of permutations taking a quadratic number of steps to reach a fixed point with the identity permutation.

• 出版日期2010-10-25