Membership testing problem
We need to describe a test for membership in , i.e., we need to construct an algorithm that can take as input the code-word for any and outputs whether or not .
Relation with other problems
Problems it reduces to
|Problem||Nature of problem||Description of reduction of membership testing to the problem|
|Order-finding problem||Suppose is a finite group described by means of an encoding. Consider a subset of . The goal is to find the order of the subgroup .||Compute the orders of the subgroups and . If the orders are the same, then . If the orders are different, then .|
Problems that are solved using it
- Subgroup testing problem: For this problem, we are given sets and inside and we are asked whether the group generated by contains the group generated by . The subgroup testing problem reduces to the membership testing problem via a positive truth-table reduction. The idea of the reduction is to check, for each element in , whether it is a member of .
- Normality testing problem: Given generating sets for and for , the problem asks whether is a normal subgroup of . The normality testing problem reduces to the membership testing problem via a positive truth-table reduction. The idea is to first use the subgroup testing problem and to then check whether every conjugate of an element in by an element in must be in .
- Normal closure-finding: This is solved using the normality testing problem
- Subnormality testing problem: This is solved using the normal closure-finding algorithm
Black-box group algorithms
These work for a group specified by means of an encoding.
|Algorithm||Additional information needed for algorithm, if any||Time taken, where is the order of the group and is the size of the generating set||Type of algorithm|
|Black-box group algorithm for finding the subgroup generated by a subset||times the time for the group operations.||deterministic|
|Nondeterministic black-box group algorithm for membership testing||nondeterministic|