**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](https://cstheory.stackexchange.com/questions/39798/is-normal-centralizer-problem-in-p)) a month back but did not get any response.



Is the Normal centralizer problem in P?
Yes. This is [Proposition 7.3](https://books.google.com/books?id=zuNgdF0RXmAC&pg=PA159) of 


Eugene M. Luks.
[Permutation groups and polynomial-time computation](http://ix.cs.uoregon.edu/~luks/dimacs.pdf).
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.


