Coset Intersection Problem

Given : $K,H \le S_n$, and $\sigma \in S_n$

Find : $K \cap H\sigma$

Known results are :

  • $n^{O(\sqrt n )}$ time algorithm by L.Babai.
  • $n^{O(1)} m^{O(\sqrt m )}$, where $m$ is the length of the longest orbits of the two groups by L.Babai.
  • exp ($O(\sqrt n \ log n))$ by L.Babai.

Problem is in $\mathsf{P\text{}}$, if subgroup $K$ is a $S_n$ or just identity element. My question is what are the other cases, where problem is easy to solve i.e. is in $\mathsf{P\text{}}$.



Your Answer

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