2
$\begingroup$

Notations

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

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 it in $P$? Give an polynomial time algorithm if answer is yes. I know that If we drop the normal condition from the above problem then problem will not be in $P$. Also note that computing normaliser of subgroup $H$ is in P.

Improve this question
$\endgroup$
2
  • $\begingroup$ How are elements of A represented? ​ ​ $\endgroup$
    – user6973
    Jan 17 '18 at 16:18
  • 1
    $\begingroup$ Now posted also on MathOverflow: Is the Normal centralizer problem in P? $\endgroup$
    – Martin
    Jan 18 '18 at 14:55