Communications of the ACM
Computer Scientists Make Progress on Math Puzzle
UT Dallas computer scientists Linda Morales and Hal Sudborough have produced a proof to the Topswops problem.
Credit: The University of Texas at Dallas
University of Texas at Dallas 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."
From University of Texas at Dallas
View Full Article
Abstracts Copyright © 2010 Information Inc., Bethesda, Maryland, USA 
No entries found