<p>Consider the complement, i.e. where you are asked to test whether $G \pi \cap H \not= \emptyset$. As I pointed out in <a href="https://cstheory.stackexchange.com/questions/25827/complexity-of-permutation-related-problems/25835#25835">this answer</a>, 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}$.</p>

<p><strong>Edit</strong>: It is shown in [2, Thm. 15] that the coset intersection problem is in $\text{NP} \cap \text{coAM}$. As noted <a href="http://www.mathunion.org/ICM/ICM1990.2/Main/icm1990.2.1479.1490.ocr.pdf" rel="nofollow noreferrer">here</a>, p. 7, the coset intersection problem is therefore not NP-complete, unless the polynomial time hierarchy collapses. Moreover, it is noted <a href="http://www.mathunion.org/ICM/ICM1990.2/Main/icm1990.2.1479.1490.ocr.pdf" rel="nofollow noreferrer">here</a>, 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.</p>

<p>[1] <a href="http://ix.cs.uoregon.edu/~luks/NC.pdf" rel="nofollow noreferrer">L. Babai, E. M. Luks &amp; A. Seress. <em>Permutation groups in NC</em>. Proc. 19th annual ACM symposium on Theory of computing, pp. 409-420, 1987.</a></p>

<p>[2]  <a href="http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf" rel="nofollow noreferrer">L. Babai, S. Moran. <em>Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes</em>. Journal of Computer and System Sciences, vol. 36, issue 2, pp. 254-276, 1988.</a></p>

CC BY-SA 3.0
2014-09-25T20:34:38.310Z
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
CC BY-SA 3.0
2014-09-25T21:06:01.433Z
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
CC BY-SA 3.0
2014-09-26T02:52:29.760Z
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
CC BY-SA 3.0
2014-09-26T17:17:16.410Z
Right, thank you. That part of my answer is pretty much worthless then.
Michael Blondin
CC BY-SA 3.0
2014-09-28T01:40:09.253Z
I removed the paragraph, it was just confusing.
Michael Blondin
CC BY-SA 3.0
2014-09-25T18:32:45.787Z
2014-09-28T01:38:38.943Z
2017-04-13T12:32:28.077Z
Michael Blondin
<p>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.)</p>

<p><a href="http://dx.doi.org/10.1145/301250.301427" rel="nofollow">Luks 1999</a> (<a href="http://ix.cs.uoregon.edu/~luks/StocHyper.pdf" rel="nofollow">free author's copy</a>) gave a $2^{O(n)}$-time algorithm, while Babai (see his 1983 Ph.D. thesis, also <a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.1983.10" rel="nofollow">Babai-Kantor-Luks FOCS 1983</a>, 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. </p>

CC BY-SA 3.0
2014-09-25T22:58:48.053Z
2014-10-07T18:08:59.687Z
2014-10-07T18:08:59.687Z
Joshua Grochow
<p>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?</p>

<p>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?</p>

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

CC BY-SA 3.0
2014-09-25T10:03:55.583Z
How are the two groups represented as input?
Emil Jeřábek
CC BY-SA 3.0
2014-09-25T10:05:00.663Z
by convention, they are given by sets of generators.
maomao
CC BY-SA 3.0
2014-09-26T20:15:55.870Z
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
CC BY-SA 3.0
2015-11-12T17:22:04.677Z
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
<cc.complexity-theory><graph-isomorphism><gr.group-theory>
Complexity of the coset intersection problem
maomao
# Complexity of the coset intersection problem

(Asked by: username_0 on 2014-09-25)

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?

**Tags:** cc.complexity-theory, graph-isomorphism, gr.group-theory
> **Comments:**
> **username_1**: How are the two groups represented as input?  
> **username_0**: by convention, they are given by sets of generators.  
> **username_2**: 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}$.  
> **username_3**: 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.  

---

## 2 answers

### Answer by username_2 on 2014-09-25. Score: 11 | Accepted answer

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](http://dx.doi.org/10.1145/301250.301427) ([free author's copy](http://ix.cs.uoregon.edu/~luks/StocHyper.pdf)) gave a $2^{O(n)}$-time algorithm, while Babai (see his 1983 Ph.D. thesis, also [Babai-Kantor-Luks FOCS 1983](http://doi.ieeecomputersociety.org/10.1109/SFCS.1983.10), 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.


---

### Answer by username_4 on 2014-09-25. Score: 9

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](https://cstheory.stackexchange.com/questions/25827/complexity-of-permutation-related-problems/25835#25835), 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](http://www.mathunion.org/ICM/ICM1990.2/Main/icm1990.2.1479.1490.ocr.pdf), p. 7, the coset intersection problem is therefore not NP-complete, unless the polynomial time hierarchy collapses. Moreover, it is noted [here](http://www.mathunion.org/ICM/ICM1990.2/Main/icm1990.2.1479.1490.ocr.pdf), 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.](http://ix.cs.uoregon.edu/~luks/NC.pdf)

[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.](http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf)

> **Comments:**
> **username_0**: 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...)  
> **username_4**: My bad, my brain mixed "normal" and "solvable" for a moment. I'm sorry. I edited the answer, I hope it answers your question.  
> **username_2**: 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).  
> **username_4**: Right, thank you. That part of my answer is pretty much worthless then.  
> **username_4**: I removed the paragraph, it was just confusing.  

---

