Double coset membership testing problem
This article describes a basic decision problem in computational group theory
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 double coset membership testing 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 double coset membership testing problem and studied a whole class of problems 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. Elements
and
in
are given (described as elements of
).
Goal
We are required to determine whether is in the double coset
, or equivalently, if
.
Because the goal can be formulated in terms of equality of double cosets, it is also termed the double coset equality problem.
Default
By default, when we refer to the membership testing problem, we refer to the membership testing problem in permutation groups, viz is the symmetric group on a finite set. For a study of the problem on linear groups, refer membership testing problem for linear groups.
In this problem, plays no particular role, and we might as well consider
and
directly as subgroups of
and
,
as elements of
.
Relation with other problems
Equivalent decision problems
- Group factorization problem: A priori, this is a special case of the double coset membership testing problem. The group factorization problem takes as input subgroups
and
(described by generating sets) and an element
in
, and outputs whether
is in
. Clearly, the group factorization problem reduces to the double coset membership problem by setting
as the identity element.
It also turns out that double coset membership testing reduces to group factorization. Template:Fill-proof
- Coset intersection problem: This is clearly equivalent to the group factorization problem. It takes as input two subgroups
and
and an element
and asks whether
∩
is nonempty.
References
- Group-theoretic algorithms and graph isomorphism by C. Hoffmann, Lecture Notes in Computer Science No. 136, Springer, 1982
- Graph Isomorphism is Low for PP by Johannes Kobler, Uwe Schoning, and Jacobo Toran, Journal of Computational Complexity, 2, 1992, 301-310