Membership testing problem

From Groupprops
(Redirected from Membership problem)
Jump to: navigation, search

Definition

Given data

G is a finite group equipped with an encoding. 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.

Relation with other problems

Problems it reduces to

Problem Nature of problem Description of reduction of membership testing to the problem
Order-finding problem Suppose G is a finite group described by means of an encoding. Consider a subset B of G. The goal is to find the order of the subgroup \langle B \rangle. Compute the orders of the subgroups H = \langle B \rangle and \langle H, g \rangle = \langle B \cup \{ g \} \rangle. If the orders are the same, then g \in H. If the orders are different, then g \notin H.

Problems that are solved using it

  • Subgroup testing problem: For this problem, we are given sets A and B inside U and we are asked whether the group G generated by A contains the group H generated by B. The subgroup testing problem reduces to the membership testing problem via a positive truth-table reduction. The idea of the reduction is to check, for each element in B, whether it is a member of G.
  • Normality testing problem: Given generating sets A for G and B for H, the problem asks whether H is a normal subgroup of G. The normality testing problem reduces to the membership testing problem via a positive truth-table reduction. The idea is to first use the subgroup testing problem and to then check whether every conjugate of an element in B by an element in A must be in B.

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

Linear group algorithms