The diameter of a group is the length of the longest product of generators required to reach a group element. We show that the diameter of a permutation group of degree n generated by cycles of bounded degree is O(n²). This bound is the best possible. Additionally, such short products can be found in polynomial time. The techniques presented here may be applied to many permutation-group puzzles such as Alexander’s Star, the Hungarian Rings, Rubik’s Cube, and some of their generalizations.

--From the Authors’ Abstract

This paper summarizes various complexity results of permutation-group theory and presents its results in a straightforward theorem/proof style. It will be of interest to group and computer science theoreticians. A knowledge of elementary group theory is assumed.