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$, for the code-word for an element in $G$.

Numbers involved

We let $n$ denote the cardinality of $G$, $l$ denote the maximum possible length of a code-word in $G$, $r$ denote the number of generators, $m$ denote the time complexity of multiplication, and $i$ denote the time complexity of inversion. We assume that $m,i,l,r$ are all polynomial in $n=\log N$.

All complexities will be measured in terms of $n=\log N$.

Black-box avatar

The black-box avatar asks for a solution to this problem that works for all encodings, and treats the group operations as black boxes. The following can be said for the black box avatar.

NP

The problem of checking membership in the subgroup is in nondeterministic polynomial-time. In other words, if $g\in H$, one can give a short proof of the fact, by constructing a circuit for outputting $g$ as an expression in the elements of $B$. This polynomial depends on the number of generators, the code-word lengths, the time for multiplication and many such factors, but since all these are polynomial in $n$, we can argue that that circuit can be constructed and checked (nondeterministcally) in polynomial time.

For full proof, refer: Membership testing is in NP

co-AM

The idea here is very similar to the general idea of showing that graph isomorphism is in co-AM.

For full proof, refer: Membership testing is in co-AM

Permutation groups avatar

In the situation where $G$ is described as a faithful permutation group, and again assuming that the size of the set on which that permutation group acts is polynomially related to $\log N$, we actually have a way of using a generating set to obtain a membership test.

Refer Membership testing problem (old) for details as of now (they'll be put up here shortly).