Membership testing problem

Definition

Given data

$G$ is a finite group equipped with an encoding $C$. $H$ is a subgroup of $G$ and we are given a generating set $B$ for $H$.

Goal

We need to describe a test for membership in $H$, i.e., we need to construct an algorithm that can take as input the code-word for any $g\in G$ and outputs whether or not $g\in H$.

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 $G$ is a finite group described by means of an encoding $C$. Consider a subset $B$ of $G$. The goal is to find the order of the subgroup $⟨B⟩$.	Compute the orders of the subgroups $H=⟨B⟩$ and $⟨H,g⟩=⟨B\cup \{g\}⟩$. If the orders are the same, then $g\in H$. If the orders are different, then $g\notin H$.

Problems that are solved using it

• Subgroup testing problem: For this problem, we are given sets $A$ and $B$ inside $U$ and we are asked whether the group $G$ generated by $A$ contains the group $H$ generated by $B$. 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 $B$, whether it is a member of $G$.

• Normality testing problem: Given generating sets $A$ for $G$ and $B$ for $H$, the problem asks whether $H$ is a normal subgroup of $G$. 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 $B$ by an element in $A$ must be in $B$.

• 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 $N$ is the order of the group and $s$ is the size of the generating set	Type of algorithm
Black-box group algorithm for finding the subgroup generated by a subset		$O(Ns)$ times the time for the group operations.	deterministic
Nondeterministic black-box group algorithm for membership testing			nondeterministic

Permutation group algorithms

• Permutation group algorithm for membership testing

Linear group algorithms

• Linear group algorithm for membership testing