Membership testing problem

Description

Given data

$G$ is a 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$.

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