Centralizer-finding problem

This article describes a group-finding problem, that is, a problem where we have to explicitly find a generating set of a group that is specified through certain conditions

Description

Given data

Our universe is some group $U$ (such as a linear group or a permutation group) in which inverses can readily be computed.

A group $G$ in $U$ is specified by a generating set $A$. An element $x$ in $U$ is specified.

Goal

We need to determine the centralizer of $x$ in $G$.

Note that since we can in particular restrict $x$ to only an element of $G$, this really solves the problem of finding the centralizer of an element of the group if it is described using a faithful linear or permutation representation.

In this article, we discuss the centralizer-finding problem for cases where $U$ is the permutation group on a finite set $S$ of size $n$.

Relation with other problems

Equivalent group-finding problems

• Group intersection problem: It turns out that the two problems are PTIME equivalent.

• Set stabilizer problem: It turns out that the two problems are PTIME equivalent. For full proof, refer: Centralizer-finding PTIME equals set stabilizer

• Partition stabilizer problem: For full proof, refer: Centralizer-finding PTIME equals partition stabilizer

Equivalent decision problems

• Conjugacy problem
• Group factorization problem
• Double coset equality problem

All the PTIME equivalences can be shown by using the fact that each is PTIME equivalent to the set stabilizer problem.