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