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

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.