10
$\begingroup$

Is there an algorithm for solving the following problem: let $g_1,\ldots,g_n$ be permutations in some (large) symmetric group, and $g$ be a permutation that is known to be in the subgroup generated by $g_1,\ldots,g_n$, can we write $g$ explicitly as a product of the $g_i$'s?

My motivation is that I'm TAing an intro abstract algebra course, and would like to use the Rubik's cube to motivate a lot of things for my students, and would, in particular, like to show them an algorithm to solve it using group theory. (That is, I can write down what permutation of the cubes I have, and want to decompose it into basic rotations, which I then invert and do in the opposite order to get back to the solved state.) Though I'm interested in the more general case, not just for the Rubik(n) groups, if a solution works out.

Note: I don't really know what keywords to use for solving this problem, if someone can point me to the right search terms to google to get the results I'm looking for, I'll gladly close this.

$\endgroup$
3
  • 2
    $\begingroup$ Have you looked at the book Adventures in Group Theory by David Joyner? I believe that a large portion of the book is devoted to applying group theory to the Rubik's cube. $\endgroup$
    – user1073
    Jan 14, 2010 at 15:25
  • $\begingroup$ Thre was a book called "Notes on Rubik's Magic Cube" by David Singmaster. I used to have a copy when I was an undergraduate in the early 80s but someone borrowed it and never returned it :( $\endgroup$ Jan 14, 2010 at 21:37
  • $\begingroup$ Jose, there's 19 copies of that book available used on a popular internet new/used book site. There's also 2 copies of his slightly-more-recent "Handbook of Cubik math". I won't endorse any particular reseller but Google Books is fast at finding some of them. $\endgroup$ Jan 15, 2010 at 4:26

2 Answers 2

11
$\begingroup$

Yes. The general rule of thumb is that groups described by permutations are computationally easy, groups described by generators and relations have computational problems that are generally undecidable, and matrix groups are somewhere in between.

There's a whole book "Permutation group algorithms" by Seress, Cambridge University Press, 2003.

The main technique for permutation groups is called the Schreier–Sims algorithm; there's a survey here, for instance. The rough idea is to stabilize the permuted elements one at a time. As Mitch already said, though, this doesn't find the shortest word in the generators that produces any particular group element, which is a more difficult problem.

$\endgroup$
1
  • 1
    $\begingroup$ I think David's answer is a bit misleading. I realize this is a belated comment, but I think there is an important technical difference here. It can indeed be determined in poly time if $g$ is in the subgroup generated by the $g_i$'s. However, the word lengths can increase exponentially so if you want to write an explicit word in $g_i$'s the Schreier–Sims is useless. Of course, sometimes the lengths are superpolynomial (take e.g. a cyclic group obtained a product of different prime cycles), but if the goal is to find a "relatively" short word when it exist, you need something else. $\endgroup$
    – Igor Pak
    Feb 17, 2010 at 7:12
9
$\begingroup$

See this paper:

http://www.dartmouth.edu/~rah/games-with-algorithms.pdf

Page 22 contains a survey of the problem you're interested in. Apparently, there is a polynomial time algorithm to check if a solution exists (it will also return some implicitly represented solution), but finding the solution with the fewest number of moves is, not surprisingly, PSPACE-complete.

The original reference is:

Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences. Theor. Comput. Sci. 36: 265-289 (1985)

$\endgroup$
2
  • 2
    $\begingroup$ What do you mean by implicitly represented? $\endgroup$ Jan 14, 2010 at 15:46
  • 2
    $\begingroup$ So, the solution could have exponential length so that you can't write it out in polynomial time. Instead you release, say, a Turing machine which on input $i$ returns the permutation $g_i$. This can be done efficiently. $\endgroup$
    – Mitch
    Jan 14, 2010 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.