Subgroup testing problem

Definition

We are working inside a universe group $U$ described by means of an encoding $C$.

We are given subgroups $G$ and $H$ of $U$, specified by generating sets ($A$ for $G$ and $B$ for $H$). The goal is to determine whether $H\leq G$.

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 $G$. Then, test whether all the elements of $B$ satisfy the test for membership in $G$.
order-finding problem	find the order of a subgroup given a generating set.	via membership testing problem