Set-stabilizer problem

From Groupprops
(Redirected from Set stabilizer problem)
Jump to: navigation, search

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:

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).