Group factorization 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
The group factorization 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 group factorization problem) that are Turing-equivalent to the double coset membership testing problem.
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 ).
Determine whether is in .
Relation with other problems
Equivalent decision problems
- Coset intersection problem: Here, two subgroups and are specified by means of generating sets. An element in is given, and we need to determine whether intersects nontrivially.
The coset equality problem is equivalent to the group factorization problem because saying that intersects nontrivially is equivalent to saying that is in .
- 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 .
The group factorization problem reduces to double coset membership testing simply by setting to be the identity element. The reduction the other way is a little more tricky: it uses the fact that if and only iff , which is a group factorization.