# Group intersection problem

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_1$ $G_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.