Coset intersection problem

From Groupprops
Jump to: navigation, search

Template:Decision 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

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 U (such as a linear group or a permutation group) in which products and inverses can be readily computed.

A group G in U is specified by a generating set A, and subgroups H and K of G are specified by means of generating sets B and C respectively. An elements x in G is given (described as an element of U).

Goal

Determine whether Hx intersects K.

Relation with other problems

Equivalent decision problems

Clearly, the coset intersection problem reduces to the double coset membership problem, because asking if Hx \cap K is nonempty is the same as asking whether the double coset HK contains x.

Conversely, given a double coset membership testing problem, wherein we want to know if x_2 \in Hx_2K, the corresponding coset equality problem is the problem of asking whether H^{x_2^{-1}}(x_2^{-1}x_1) \cap K is nonempty.