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$)?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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).
-
$\begingroup$ When did Mulmuley work on permutation group algorithms? (Other than the Kronecker problem, which is arguably a very different kind of thing...) $\endgroup$ Commented May 11, 2015 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$ Commented May 11, 2015 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$ Commented May 11, 2015 at 19:46
$\begingroup$
$\endgroup$
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.
answered May 10, 2015 at 14:30