4
$\begingroup$

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.

$\endgroup$
19
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.