# Complexity of computing the order of a permutation group

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$)?

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).

• When did Mulmuley work on permutation group algorithms? (Other than the Kronecker problem, which is arguably a very different kind of thing...) – Joshua Grochow May 11 '15 at 16:37
• 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. – Michael Blondin May 11 '15 at 18:27
• Fair enough (it looks like he didn't know he was working on permutation group algorithm, but Cook-McKenzie showed it was equivalent). – Joshua Grochow May 11 '15 at 19:46

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.