Colloquium Details
Rubik's Cube, Groups, and Computational Complexity
| Author: | Eugene Luks University of Oregon |
|---|---|
| Date: | June 03, 2010 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
| Host: | UO ACM Chapter |
Abstract
How do you write a program to solve the 15-Puzzle? How about Rubik's Cube or even Rubik's Revenge? Even more basic is testing whether such puzzles are solvable. These are instances of the Permutation-Group-Membership (PGM) problem, a fundamental issue in computational group theory. An algorithm discovered around 1965 has been improved to time O(n^5), which has long been conjectured to be the lower bound for PGM. But are there asymptotically-faster methods? Are they parallelizable? Surprisingly, such breakthroughs only recently became available through the completion of the monumental Classification of Finite Simple Groups.
On the other hand, commercial variants of the 15-puzzle and Rubik's Cube illustrate problems for which even polynomial time is in doubt, and they may even suggest something about the "P=NP" problem.
Biography
After earning a PhD in Mathematics from MIT, Eugene Luks held faculty positions in Mathematics at Tufts University and Bucknell University before coming to UO in 1983. Since moving into theoretical computer science, his research has mostly been in algebraic algorithms and complexity. For work in this area, Professor Luks was awarded the Delbert Ray Fulkerson Prize in Discrete Mathematics by the Mathematical Programming Society and the American Mathematical Society.
