# Coset intersection 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*

## Contents

## History

The **coset intersection problem** was introduced by Hoffmann in his paper *Group-theoretic methods in graph isomorphism* published in 1982. Hoffmann showed that graph isomorphism was a special case of a problem called the double coset membership testing problem and studied a whole class of problems (including the coset intersection problem) that are Turing-equivalent to the double coset membership testing problem.

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

A group in is specified by a generating set , and subgroups and of are specified by means of generating sets and respectively. An elements in is given (described as an element of ).

### Goal

Determine whether intersects .

## Relation with other problems

### Equivalent decision problems

- Group factorization problem: This asks whether . The group factorization problem is clearly equivalent to the coset intersection problem, because is nonempty.
- Double coset membership testing problem: Here, two subgroups and are specified by means of generating sets, and elements and are given. We need to check whether is in .

Clearly, the coset intersection problem reduces to the double coset membership problem, because asking if is nonempty is the same as asking whether the double coset contains .

Conversely, given a double coset membership testing problem, wherein we want to know if , the corresponding coset equality problem is the problem of asking whether is nonempty.