Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
