10
$\begingroup$

Given two permutations $g$ and $h$ over $n$ elements (i.e., members of $S_n$), what is the complexity of computing the order of the subgroup generated by $g,h$? Or just of deciding whether the subgroup is of order $n!$ (i.e., all of $S_n$)?

$\endgroup$
9
$\begingroup$

As a complement to Joshua Grochow's answer:

Computing the order of a permutation group given generators is in P by Schreier–Sims algorithm, see also p. 8-9 of these lectures notes by Luks. Just as membership in permutation groups, the problem was believed to be P-complete by many researchers, but it was finally shown to be in NC by Babai, Luks & Seress.

The complexity of problems for permutation groups was extensively studied and their complexity was gradually settled for abelian groups, nilpotent groups, solvable groups, groups with bounded non-abelian composition factors, and finally groups (see work by Babai, Cook, Furst, Hopcroft, Luks, McKenzie, Mulmuley, Seress and many more).

$\endgroup$
  • $\begingroup$ When did Mulmuley work on permutation group algorithms? (Other than the Kronecker problem, which is arguably a very different kind of thing...) $\endgroup$ – Joshua Grochow May 11 '15 at 16:37
  • $\begingroup$ Perhaps I should not have included him in the list, but I was referring to this paper: link.springer.com/article/10.1007%2FBF02579205 that allowed results on permutation groups, in particular for this paper of Cook & McKenzie: epubs.siam.org/doi/abs/10.1137/0216058. $\endgroup$ – Michael Blondin May 11 '15 at 18:27
  • $\begingroup$ Fair enough (it looks like he didn't know he was working on permutation group algorithm, but Cook-McKenzie showed it was equivalent). $\endgroup$ – Joshua Grochow May 11 '15 at 19:46
12
$\begingroup$

The order of permutation groups can be computed in polynomial-time. In fact, I believe even in $\mathsf{NC}$ and also nearly linear Las Vegas time. See, e.g., the book by Seress.

For reference, subgroups of $S_n$ (and algorithms related thereto) are typically called "permutation groups" rather than merely "subgroups (of $S_n$)". So you can google "permutation group algorithms" etc.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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