This problem is polynomial-time equivalent to the following basic problem: Group intersection problem
- A group acting faithfully on a finite set , is specified by a generating set (where each element of is specified as a permutation)
- A subset of is given
We need to find the subgroup of comprising those elements that map every element of to inside .
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 .For full proof, refer: Conjugacy problem PTIME equals set stabilizer
- The group factorization problem: This is a decision problem that, given two subgroups and of the symmetric group, and an element of the symmetric group, asks whether is in .
Equivalent group-finding problems
- Group intersection problem: The set stabilizer problem can be viewed as a group intersection problem where one group is and the other group is × (that is, the stabilizer of in the whole of . 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 of , we give a partition of viz as a disjoint union of subsets, and are required to find the subgroup of 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 acting on the set of vertex pairs, and the set as the set of edges (viewed as a subset of the set of vertex pairs).