# Complexity of permutation group intersection

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?

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, 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$$?
• Amazing answer, thanks! Fascinating that there is relatively recent progress on such a seemingly "off-the-shelf" problem. Commented Jul 18 at 19:14