Membership testing problem
From Groupprops
(Redirected from Membership problem)
Contents
Definition
Given data
is a finite group equipped with an encoding.
is a subgroup of
and we are given a generating set
for
.
Goal
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 ![]() ![]() ![]() ![]() |
Compute the orders of the subgroups ![]() ![]() ![]() ![]() |
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
Algorithms
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 ![]() ![]() |
Type of algorithm |
---|---|---|---|
Black-box group algorithm for finding the subgroup generated by a subset | ![]() |
deterministic | |
Nondeterministic black-box group algorithm for membership testing | nondeterministic |