Subgroup testing problem

From Groupprops
Jump to: navigation, search

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 \le 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