Skip to main content
2 of 2
added link to version on the author's website and also Google Books link
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Yes. This is Proposition 7.3 of

Eugene M. Luks. Permutation groups and polynomial-time computation. Pages 139-175 of: Larry Finkelstein and William M. Kantor, editors. Groups and Computation, Volume 11 of Amer. Math. Soc. DIMACS Series. (DIMACS, 1991), 1993.

If you drop the condition that $G$ normalizes $H$, then it is unknown whether the problem is in P (so your statement that it is not in P is too strong).

I don't know what you mean by "computing the normalizer of subgroup $H$ is in P". The normalizer in what? Computing the normalizer of $G$ in ${\rm Sym}(\Omega)$ is very unlikely to be in P. It is not even known whether this can be done in simply exponential time.

Derek Holt
  • 37.4k
  • 4
  • 95
  • 149