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