Our universe is some group (such as a linear group or a permutation group) in which inverses can readily be computed.
A group in is specified by a generating set . An element in is specified.
We need to determine the centralizer of in .
Note that since we can in particular restrict to only an element of , 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 is the permutation group on a finite set of size .
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
All the PTIME equivalences can be shown by using the fact that each is PTIME equivalent to the set stabilizer problem.