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?

  • 2
    $\begingroup$ How are the two groups represented as input? $\endgroup$ Sep 25, 2014 at 10:03
  • 1
    $\begingroup$ by convention, they are given by sets of generators. $\endgroup$
    – maomao
    Sep 25, 2014 at 10:05
  • 1
    $\begingroup$ 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}$. $\endgroup$ Sep 26, 2014 at 20:15
  • $\begingroup$ 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. $\endgroup$
    – Perry
    Nov 12, 2015 at 17:22

2 Answers 2


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.

[1] L. Babai, E. M. Luks & A. Seress. Permutation groups in NC. Proc. 19th annual ACM symposium on Theory of computing, pp. 409-420, 1987.

[2] L. Babai, S. Moran. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, vol. 36, issue 2, pp. 254-276, 1988.

  • $\begingroup$ 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...) $\endgroup$
    – maomao
    Sep 25, 2014 at 20:34
  • $\begingroup$ My bad, my brain mixed "normal" and "solvable" for a moment. I'm sorry. I edited the answer, I hope it answers your question. $\endgroup$ Sep 25, 2014 at 21:06
  • 1
    $\begingroup$ 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). $\endgroup$ Sep 26, 2014 at 2:52
  • $\begingroup$ Right, thank you. That part of my answer is pretty much worthless then. $\endgroup$ Sep 26, 2014 at 17:17
  • $\begingroup$ I removed the paragraph, it was just confusing. $\endgroup$ Sep 28, 2014 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.