# 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 group*Template:Presentation-setup at

## Contents

## Description

### Given data

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

Two groups and in are specified by means of their generating sets and .

### Goal

We are required to determine a generating set for ∩ .

## Relation with other problems

### Problems that can be solved using it

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

The set-stabilizer problem reduces many-one to the group intersection problem as follows: the set stabilizer of in is the intersection of with the set-stabilizer of in . The latter group is simply × .

- 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

- Normalizing group intersection problem: This can be solved for permutation groups
- Subnormalizing group intersection problem: This can also be solved for permutation groups