Skip to main content
MathOverflow

Return to Answer

added link to version on the author's website and also Google Books link
Source Link
Martin Sleziak
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Yes. This is Proposition 7.3Proposition 7.3 of

Eugene M. Luks. Permutation groups and polynomial-time computationPermutation 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.

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.

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.

Source Link
Derek Holt
Derek Holt
  • 37.4k
  • 4
  • 95
  • 149

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.