# Complexity of the coset intersection problem

Given the symmetry group $S_n$ and two subgroups $G, H\leq S_n$, and $\pi\in S_n$, does $G\pi\cap H=\emptyset$ hold?

As far as I know, the problem is known as the coset intersection problem. I am wondering what's the complexity? In particular, is this problem known to be in coAM?

Moreover, if $H$ is restricted to be abelian, what does the complexity become?

• How are the two groups represented as input? – Emil Jeřábek Sep 25 '14 at 10:03
• by convention, they are given by sets of generators. – maomao Sep 25 '14 at 10:05
• The coset intersection problem is typically phrased oppositely: the answer is yes iff they intersect. It is this version of the problem that's in $\mathsf{NP} \cap \mathsf{coAM}$. – Joshua Grochow Sep 26 '14 at 20:15
• An interesting side note, which invalidates none of the above: graph isomorphism, coset intersection, and string isomorphism were all the subject of a new result by Babai first described in a seminar a couple of days ago. No publication yet, but it looks like there is now a quasi-polynomial algorithm for all of them. – Perry Nov 12 '15 at 17:22

Moderately exponential time and $\mathsf{coAM}$ (for the opposite of the problem as stated: Coset Intersection is typically considered to have a "yes" answer if the cosets intersect, opposite of how it's stated in the OQ.)

Luks 1999 (free author's copy) gave a $2^{O(n)}$-time algorithm, while Babai (see his 1983 Ph.D. thesis, also Babai-Kantor-Luks FOCS 1983, and a to-appear journal version) gave a $2^{\tilde{O}(\sqrt{n})}$-time algorithm, which remains the best known to date. Since graph isomorphism reduces to quadratic-sized coset intersection, improving this to $2^{\tilde{O}(n^{1/4-\epsilon})}$ would improve the state of the art for graph isomorphism.

Consider the complement, i.e. where you are asked to test whether $G \pi \cap H \not= \emptyset$. As I pointed out in this answer, testing whether $g \in \langle g_1, \ldots, g_k\rangle$ is in $\text{NC} \subseteq \text{P}$ [1]. So you can guess $g, h \in S_n$ and test in polynomial time whether $g \in G$, $h \in H$ and $g \pi = h$. This yields an $\text{NP}$ upper bound and, therefore, your problem is in $\text{coNP}$.

Edit: It is shown in [2, Thm. 15] that the coset intersection problem is in $\text{NP} \cap \text{coAM}$. As noted here, p. 7, the coset intersection problem is therefore not NP-complete, unless the polynomial time hierarchy collapses. Moreover, it is noted here, p. 6, that it was shown by Luks that the problem is in $\text{P}$ when $H$ is solvable, which include the case of $H$ abelian.

• many thanks for the answer. For the case H is a normal subgroup, it is clear. However, if H is just abelian, it is not really clear for me. Does $GH=<{st: s\in S, t\in T}>$ still hold? (sorry for my stupidity...) – maomao Sep 25 '14 at 20:34
• My bad, my brain mixed "normal" and "solvable" for a moment. I'm sorry. I edited the answer, I hope it answers your question. – Michael Blondin Sep 25 '14 at 21:06
• When H is a normal subgroup of G, the coset intersection problem is much easier: it reduces to just the membership problem (is $\pi$ in G). – Joshua Grochow Sep 26 '14 at 2:52
• Right, thank you. That part of my answer is pretty much worthless then. – Michael Blondin Sep 26 '14 at 17:17
• I removed the paragraph, it was just confusing. – Michael Blondin Sep 28 '14 at 1:40