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
    How are the two groups represented as input? – Emil Jeřábek Sep 25 '14 at 10:03
  • 1
    by convention, they are given by sets of generators. – maomao Sep 25 '14 at 10:05
  • 1
    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
up vote 11 down vote accepted

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.

  • 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
  • 1
    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

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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