Subgroup property testing problem

This article is about a general term. A list of important particular cases (instances) is available at Category: Subgroup property testing problems

The discussion of complexity for this algorithm makes the log-size assumption: namely, the length of the maximum code-word, the time for multiplication and the time for inversion are all logarithmic in the group size

Description

Given a subgroup property $p$, the subgroup property testing problem for $p$ is the problem of determining whether a subgroup of a group satisfies $p$ in the group.

The precise nature of the subgroup property testing problem depends, of course, on the way in which we describe the group and the subgroup. Note that there are two levels at which we have choices -- we have choices for the format in which to specify $G$, and we have choices for the format in which to specify the subgroup $H$ of $G$.

The black-box encoding

Black-box problem encoding with a membership test

The black-box subgroup property testing problem for a property $p$ is solved by an algorithm which doesthe following:

It takes as input a group described via an encoding, and a subgroup of the group described via a membership test. Now, using only subroutine calls to the encoding (that is, without seeing the internal workings ofthe multiplication and inversion maps), the algorithm outputs Yes if the subgroup satisfies $p$ in the group and No otherwise.

Black-box problem encoding with a generating set

Here, in addition to the encoding of the group, we are given a generating set for the group and for the subgroup.

Black-box problem encoding with both a membership test and a generating set

Here, we are given:

• Encoding of the group
• Membership test for the subgroup (which runs in polynomial time in the log-size)
• Generating set for the group
• Generating set for the subgroup