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

## Contents

## Description

### Given data

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.

### Goal

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.