Group intersection problem

From Groupprops
Jump to: navigation, search
This article describes the subgroup operator computation problem for the subgroup operator: [[subgroup intersection]]

This problem is polynomial-time equivalent to the following basic problem: Set stabilizer problem

This article describes a problem in the setup where the group(s) involved is/are defined by means of an embedding in a suitable universe group (such as a linear or a permutation group) -- viz in terms of generators described as elements sitting inside this universe groupTemplate:Presentation-setup at

Description

Given data

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

Two groups G_1 and G_2 in U are specified by means of their generating sets A_1 and A_2.

Goal

We are required to determine a generating set for G_1G_2.

Relation with other problems

Problems that can be solved using it

  • Set-stabilizer problem: This problem asks us to compute, for a group G acting faithfully on a set S, the set-stabilizer of a subset T of S within G. Here, G is given by a generating set A of permutations.

The set-stabilizer problem reduces many-one to the group intersection problem as follows: the set stabilizer of T in G is the intersection of G with the set-stabilizer of T in Sym(S). The latter group is simply Sym(T) × Sym(S- T).

  • Graph-automorphism finding: This problem asks us to compute the automorphism group of a graph. Graph-automorphism finding has a many-one reduction to the set-stabilizer problem, and hence, by the transitivity of many-one reductions, it has a many-one reduction to the group intersection problem.
  • Graph isomorphism: The decision problem of graph isomorphism can be solved using graph-automorphism finding, and hence, using the group intersection problem.

Easier problems