# 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 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

## 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 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 |