Blog: Computer Scientists Make Progress on Math Puzzle

Computer Scientists Make Progress on Math Puzzle
UT Dallas News (10/28/10) David Moore

University of Texas at Dallas (UTD) professors Linda Morales and Hal Sudborough have made progress on the Topswops mathematical puzzle. Stanford University computer scientist Donald Knuth previously proved an exponential upper bound on the number of Topswops steps, but Morales and Sudborough proved a lower bound that is better than that proposed in Knuth's conjecture. "What I find fascinating about a problem such as bounding the Topswops function is connected to its simplicity, to its fundamental nature, and to the complexity and difficulty of finding an answer," Sudborough says. "Our research uncovered permutations whose iterate sequences have a fascinating structure, which upon analysis have revealed hitherto unknown lower bounds for the problem," Morales says. Knuth called their proof technique both "elegant" and "amazing." "There is much more to learn from the problem," Morales says. "We have tantalizing hints of more revelations just waiting to be uncovered."

View Full Article