Centralizer-finding problem

From Groupprops
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

Description

Given data

Our universe is some group U (such as a linear group or a permutation group) in which inverses can readily be computed.

A group G in U is specified by a generating set A. An element x in U is specified.

Goal

We need to determine the centralizer of x in G.

Note that since we can in particular restrict x to only an element of G, 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 U is the permutation group on a finite set S of size n.

Relation with other problems

Equivalent group-finding problems

Equivalent decision problems

All the PTIME equivalences can be shown by using the fact that each is PTIME equivalent to the set stabilizer problem.