<p>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., <a href="http://www.ams.org/mathscinet-getitem?mr=1970241">the book by Seress</a>. </p>

<p>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.</p>

CC BY-SA 3.0
2015-05-10T14:30:53.937Z
2015-05-10T14:30:53.937Z
Joshua Grochow
<p>As a complement to Joshua Grochow's answer:</p>

<p>Computing the order of a permutation group given generators is in P by <a href="https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm">Schreier–Sims algorithm</a>, see also p. 8-9 of <a href="http://ix.cs.uoregon.edu/~luks/northeasterncourse.pdf">these lectures notes</a> 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 <a href="http://ix.cs.uoregon.edu/~luks/NC.pdf">Babai, Luks &amp; Seress</a>.</p>

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

CC BY-SA 3.0
2015-05-11T16:37:45.097Z
When did Mulmuley work on permutation group algorithms? (Other than the Kronecker problem, which is arguably a very different kind of thing...)
Joshua Grochow
CC BY-SA 3.0
2015-05-11T18:27:51.767Z
Perhaps I should not have included him in the list, but I was referring to this paper: http://link.springer.com/article/10.1007%2FBF02579205 that allowed results on permutation groups, in particular for this paper of Cook & McKenzie: http://epubs.siam.org/doi/abs/10.1137/0216058.
Michael Blondin
CC BY-SA 3.0
2015-05-11T19:46:14.530Z
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
CC BY-SA 3.0
2015-05-10T22:30:34.777Z
2015-05-10T23:16:07.290Z
2015-05-10T23:16:07.290Z
Michael Blondin
<p>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$)?</p>

<cc.complexity-theory><algebra><gr.group-theory>
Complexity of computing the order of a permutation group
Aryeh
# Complexity of computing the order of a permutation group

(Asked by: username_0 on 2015-05-10)

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

**Tags:** cc.complexity-theory, algebra, gr.group-theory

---

## 2 answers

### Answer by username_2 on 2015-05-10. Score: 10 | Accepted answer

As a complement to Joshua Grochow's answer:

Computing the order of a permutation group given generators is in P by [Schreier–Sims algorithm](https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm), see also p. 8-9 of [these lectures notes](http://ix.cs.uoregon.edu/~luks/northeasterncourse.pdf) 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](http://ix.cs.uoregon.edu/~luks/NC.pdf).

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

> **Comments:**
> **username_1**: When did Mulmuley work on permutation group algorithms? (Other than the Kronecker problem, which is arguably a very different kind of thing...)  
> **username_2**: Perhaps I should not have included him in the list, but I was referring to this paper: http://link.springer.com/article/10.1007%2FBF02579205 that allowed results on permutation groups, in particular for this paper of Cook & McKenzie: http://epubs.siam.org/doi/abs/10.1137/0216058.  
> **username_1**: Fair enough (it looks like he didn't know he was working on permutation group algorithm, but Cook-McKenzie showed it was equivalent).  

---

### Answer by username_1 on 2015-05-10. Score: 12

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](http://www.ams.org/mathscinet-getitem?mr=1970241).

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.


---

