Is the Normal centralizer problem in P?

Question

Notation

1. $\le$ is used for the subgroup relation;
2. $P$ means polynomial time in input size;
3. $\Omega = \{1,2,3,\cdots,n\}$ is a input domain;
4. $\mathrm{Sym}(\Omega)$ means the symmetric group on $\Omega$;
5. $G = \langle A \rangle $ means the subgroup $G$ generated by the subset $A$ of $\mathrm{Sym}(\Omega)$.

---

The normal centralizer problem is defined as follows:

Given: $G = \langle A \rangle, H = \langle B \rangle \le \text{Sym}(\Omega)$, where $G$ normalizes $H$.

Find : $C_G(H) = \{g \in G \mid gh =hg, \forall h \in H\}$

---

Question : Is this problem in $P$? Give a polynomial time algorithm if answer is yes. I know that if we drop the normal condition from the above problem then the new version will not be in $P$. Also note that computing the normalizer of a subgroup $H$ is in P.

Please note that I have asked the same question on theoretical computer science exchange (link) a month back but did not get any response.

Answer 1

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.