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.

|cite|improve this question
$\endgroup$

closed as off-topic by Lev Reyzin♦ Jan 27 '18 at 18:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Our site policy prohibits simultaneous crossposting: it duplicates effort and fractures discussion. Crossposting is permitted after a week has passed without a satisfying answer elsewhere. When crossposting please summarize the relevant discussions from other sites in your question and link between the copies in both directions." – Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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