Subgroup testing problem
We are working inside a universe group described by means of an encoding .
We are given subgroups and of , specified by generating sets ( for and for ). The goal is to determine whether .
Relation with other problems
Problems it reduces to
|Problem||Description||Description of reduction|
|membership testing problem||given a generating set for a subgroup, find a membership test for the subgroup.||black-box reduction of subgroup testing problem to membership testing problem: First, use the membership testing problem to obtain a membership test for the group . Then, test whether all the elements of satisfy the test for membership in .|
|order-finding problem||find the order of a subgroup given a generating set.||via membership testing problem|