<p><strong>Notations</strong> </p>

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

<hr>

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

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

<hr>

<p><strong>Question :</strong> 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.</p>

CC BY-SA 3.0
2018-01-18T14:55:00.877Z
Now posted also on MathOverflow: [Is the Normal centralizer problem in P?](https://mathoverflow.net/q/290941)
Martin
<cc.complexity-theory><ds.algorithms>
Is Normal centralizer problem in P?
new
# Is Normal centralizer problem in P?

(Asked by: username_0 on 2017-12-19)

**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.

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: Now posted also on MathOverflow: [Is the Normal centralizer problem in P?](https://mathoverflow.net/q/290941)  

---

## 0 answers

