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 complexity of subgroup property testing problems is typically studied under the log-size assumption.

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 does the 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. We are not given any explicit membership test 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

Black-box problem encoding with a random sampler

Here, in addition to the encoding of the group, we are given an algorithm that samples randomly, in a near-uniform manner this notion needs to be made precise, from the elements of the subgroup.

Relation with the membership testing problem

Nondeterministic and co-nondeterministic reductions

A subgroup property is a first-order subgroup property if its satisfaction can be expressed as a first-order formula over the language of groups. First-order subgroup properties are important in the sense that the problem of subgroup property testing for these reduces to the membership testing problem via nondeterministic and co-nondeterministic reductions. More precisely, any subgroup property expressible by a ${\mathrm{\Sigma }}_n$ formula lies in ${\mathrm{\Sigma }}_n(P^{Membershiptesting})$ and the same for ${\mathrm{\Pi }}_n$.

Note, however, that for an arbitrary first-order subgroup property, we may not always be able to guarantee that having a uniform random sampler or a generating set could exist.

Randomized reductions

All first-order subgroup properties may not succumb well to randomized reductions. In general, a first-order subgroup property gives a good randomized reduction if the fraction of examples for the existentially quantified clauses is large enough, and the fraction of counterexamples in case a universally quantified clause is not satisfied, is also large enough.

Deterministic reductions

In the deterministic reductions, we do not check the quantified variables over all values, rather, we check over a small and strategically chosen subset of the group. This approach works if we are somehow guaranteed that the formula being valid on that strategically chosen subset guarantees its being valid everywhere.

This for instance happens with the normality testing problem.