# Set-stabilizer problem

(Redirected from Set stabilizer 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

This problem is polynomial-time equivalent to the following basic problem: Group intersection problem

## Description

### Given data

• A group $G$ acting faithfully on a finite set $S$, is specified by a generating set $A$ (where each element of $A$ is specified as a permutation)
• A subset $T$ of $S$ is given

### Goal

We need to find the subgroup of $G$ comprising those elements that map every element of $T$ to inside $T$.

## Relation with other problems

### Equivalent decision problems

The set stabilizer problem is polynomial-time equivalent to the following decision problems:

• The set transporter problem: This is a decision problem which asks whether, for a group action on a set, one given subset can be transported to another. For full proof, refer: Set transporter PTIME equals set stabilizer
• The conjugacy problem: This is a decision problem which asks whether two given elements in the whole symmetric group are conjugate in the subgroup $G$.For full proof, refer: Conjugacy problem PTIME equals set stabilizer
• The group factorization problem: This is a decision problem that, given two subgroups $G$ and $H$ of the symmetric group, and an element $x$ of the symmetric group, asks whether $x$ is in $GH$.

### Equivalent group-finding problems

• Group intersection problem: The set stabilizer problem can be viewed as a group intersection problem where one group is $G$ and the other group is $Sym(T)$ × $Sym(T^c)$ (that is, the stabilizer of $T$ in the whole of $Sym(S)$. The converse is also true: any group intersection problem can be viewed as a set stabilizer problem for the diagonal in an action on the square space. For full proof, refer: Group intersection PTIME equals set stabilizer
• The partition stabilizer problem: Here, instead of giving a subset $T$ of $S$, we give a partition of $S$ viz $S$ as a disjoint union of subsets, and are required to find the subgroup of $G$ comprising those elements that preserve the partition (though they may not preserve individual sets in the partition).
• The centralizer-finding problem: This is a group-finding problem that takes as input an element of the symmetric group on a finite set and outputs a generating set for the centralizer of that element.

For full proof, refer: Centralizer-finding PTIME equals set stabilizer

### Problems that reduce to it

• Graph automorphism-finding: This problem takes as input a graph and outputs a generating set for the automorphism group of that graph, with the generators specified as permutations on the vertex set of the graph. This reduces to the set stabilizer problem by viewing the permutation group of the vertex set as the group $G$ acting on the set of vertex pairs, and the set $S$ as the set of edges (viewed as a subset of the set of vertex pairs).