<p>tl;dr: Babai's 2016 algorithm solves this in quasi-polynomial time in theory. In practice, different heuristic methods are used and are considered to mostly solve it efficiently.</p>
<p>Details:</p>
<p>In Seress's book <a href="https://doi.org/10.1017/CBO9780511546549" rel="noreferrer">Permutation Group Algorithms</a>, he says &quot;Although all known algorithms [this was prior to Babai's] for these problems have exponential worst-case complexity, they are not considered difficult in practice&quot;. In Section 9.1.2 of that book Seress discusses heuristics that are used in combination with backtracking methods that solve the problem in practice.</p>
<p>In terms of &quot;complexity classes&quot;, intersecting two permutation groups is one of a whole host of problems that appear &quot;just above&quot; graph isomorphism in complexity, but that are all equivalent to one another. I say &quot;just above&quot; because, while they are formally GI-hard, many known algorithms (including Babai's) for GI in fact work for this larger class of problems, even though they are not known to reduce to GI. This class should probably have a name, but alas.</p>
<p>Luks (&quot;Permutation groups and polynomial-time computation&quot;, DIMACS Series in Discrete Math and Theoret. Comp. Sci., Vol. 11, 1993) showed that the following prolems are all poly-time equivalent. All subgroups of <span class="math-container">$S_n$</span> here are given by generating sets of permutations.</p>
<ol>
<li>Intersect two subgroups of <span class="math-container">$S_n$</span></li>
<li>Set stabilizer: given <span class="math-container">$G \leq S_n$</span> and <span class="math-container">$\Delta \subseteq [n]$</span>, find (generators of) the setwise stabilizer of <span class="math-container">$\Delta$</span>, namely <span class="math-container">$\{g : \Delta^g = \Delta\}$</span>.</li>
<li>Given <span class="math-container">$G \leq S_n, x \in S_n$</span>, find the centralizer <span class="math-container">$C_G(x)$</span></li>
<li>Set transporter: given <span class="math-container">$G \leq S_n$</span> and <span class="math-container">$\Delta_1, \Delta_2 \subseteq [n]$</span>, decide if there is <span class="math-container">$g \in G$</span> such that <span class="math-container">$\Delta_1^g = \Delta_2$</span></li>
<li>Double coset equality: Given <span class="math-container">$G, H \leq S_n$</span> and <span class="math-container">$x,y \in S_n$</span>, is <span class="math-container">$GxH = GyH$</span>?</li>
<li>Conjugacy: given <span class="math-container">$G \leq S_n$</span> and <span class="math-container">$x,y \in S_n$</span>, is there some <span class="math-container">$g \in G$</span> such that <span class="math-container">$gxg^{-1} = y$</span>?</li>
</ol>

CC BY-SA 4.0
2024-07-18T19:14:53.960Z
Amazing answer, thanks! Fascinating that there is relatively recent progress on such a seemingly "off-the-shelf" problem.
Julius Kunze
CC BY-SA 4.0
2024-07-18T16:11:28.140Z
2024-07-18T16:11:28.140Z
Joshua Grochow
<p>Given generating sets for two subgroups of some finite symmetric group <span class="math-container">$S_n$</span>, what is known about the complexity of computing a generating set of their group intersection?</p>
<p>Of course, we can brute-force this by enumerating the two groups and intersecting them. For large groups, this is slow. If our generating sets are small, is there a better way?</p>

<gr.group-theory>
Complexity of permutation group intersection
Julius Kunze
# Complexity of permutation group intersection

(Asked by: username_0 on 2024-07-18)

Given generating sets for two subgroups of some finite symmetric group $S\_n$, what is known about the complexity of computing a generating set of their group intersection?

Of course, we can brute-force this by enumerating the two groups and intersecting them. For large groups, this is slow. If our generating sets are small, is there a better way?

**Tags:** gr.group-theory

---

## 1 answers

### Answer by username_1 on 2024-07-18. Score: 5 | Accepted answer

tl;dr: Babai's 2016 algorithm solves this in quasi-polynomial time in theory. In practice, different heuristic methods are used and are considered to mostly solve it efficiently.

Details:

In Seress's book [Permutation Group Algorithms](https://doi.org/10.1017/CBO9780511546549), he says "Although all known algorithms [this was prior to Babai's] for these problems have exponential worst-case complexity, they are not considered difficult in practice". In Section 9.1.2 of that book Seress discusses heuristics that are used in combination with backtracking methods that solve the problem in practice.

In terms of "complexity classes", intersecting two permutation groups is one of a whole host of problems that appear "just above" graph isomorphism in complexity, but that are all equivalent to one another. I say "just above" because, while they are formally GI-hard, many known algorithms (including Babai's) for GI in fact work for this larger class of problems, even though they are not known to reduce to GI. This class should probably have a name, but alas.

Luks ("Permutation groups and polynomial-time computation", DIMACS Series in Discrete Math and Theoret. Comp. Sci., Vol. 11, 1993) showed that the following prolems are all poly-time equivalent. All subgroups of $S\_n$ here are given by generating sets of permutations.

1. Intersect two subgroups of $S\_n$
2. Set stabilizer: given $G \leq S\_n$ and $\Delta \subseteq [n]$, find (generators of) the setwise stabilizer of $\Delta$, namely $\{g : \Delta^g = \Delta\}$.
3. Given $G \leq S\_n, x \in S\_n$, find the centralizer $C\_G(x)$
4. Set transporter: given $G \leq S\_n$ and $\Delta\_1, \Delta\_2 \subseteq [n]$, decide if there is $g \in G$ such that $\Delta\_1^g = \Delta\_2$
5. Double coset equality: Given $G, H \leq S\_n$ and $x,y \in S\_n$, is $GxH = GyH$?
6. Conjugacy: given $G \leq S\_n$ and $x,y \in S\_n$, is there some $g \in G$ such that $gxg^{-1} = y$?

> **Comments:**
> **username_0**: Amazing answer, thanks! Fascinating that there is relatively recent progress on such a seemingly "off-the-shelf" problem.  

---

