1
$\begingroup$

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{}}$.

Improve this question
$\endgroup$
2

0

Reset to default

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.