Membership testing problem: Difference between revisions

Latest revision as of 20:14, 25 June 2013

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 $⟨ B ⟩$ .	Compute the orders of the subgroups $H = ⟨ B ⟩$ and $⟨ H, g ⟩ = ⟨ B \cup {g} ⟩$ . 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$ .

Normal closure-finding: This is solved using the normality testing problem

Subnormality testing problem: This is solved using the normal closure-finding algorithm

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 (N s)$ times the time for the group operations.	deterministic
Nondeterministic black-box group algorithm for membership testing			nondeterministic

Permutation group algorithms

Permutation group algorithm for membership testing

Linear group algorithms

Linear group algorithm for membership testing

@@ Line 1: / Line 1: @@
-==Description==
+==Definition==
 ===Given data===
-<math>G</math> is a [[group]] equipped with an [[encoding of a group|encoding]] <math>C</math>. <math>H</math> is a subgroup of <math>G</math> and we are given a [[generating set]] <math>B</math> for <math>H</math>.
+<math>G</math> is a [[finite group]] equipped with an [[encoding of a group|encoding]]. <math>H</math> is a subgroup of <math>G</math> and we are given a [[generating set]] <math>B</math> for <math>H</math>.
 ===Goal===
-We need to describe a test for membership in <math>H</math>, for the code-word for an element in <math>G</math>.
+We need to describe a test for membership in <math>H</math>, i.e., we need to construct an algorithm that can take as input the code-word for any <math>g \in G</math> and outputs whether or not <math>g \in H</math>.
-===Numbers involved===
+==Relation with other problems==
-We let <math>n</math> denote the cardinality of <math>G</math>, <math>l</math> denote the maximum possible length of a code-word in <math>G</math>, <math>r</math> denote the number of generators, <math>m</math> denote the time complexity of multiplication, and <math>i</math> denote the time complexity of inversion. We assume that <math>m, i, l, r</math> are all polynomial in <math>n = \log N</math>.
+===Problems it reduces to===
-All complexities will be measured in terms of <math>n = \log N</math>.
+{| class="sortable" border="1="
+! Problem !! Nature of problem !! Description of reduction of membership testing to the problem
+|-
+| [[Order-finding problem]] || Suppose <math>G</math> is a finite group described by means of an encoding. Consider a subset <math>B</math> of <matH>G</math>. The goal is to find the order of the subgroup <math>\langle B \rangle</math>. || Compute the orders of the subgroups <math>H = \langle B \rangle</math> and <math>\langle H, g \rangle = \langle B \cup \{ g \} \rangle</math>. If the orders are the same, then <math>g \in H</math>. If the orders are different, then <math>g \notin H</math>.
+|}
+===Problems that are solved using it===
-==Black-box avatar==
+* [[Subgroup testing problem]]: For this problem, we are given sets <math>A</math> and <math>B</math> inside <math>U</math> and we are asked whether the group <math>G</math> generated by <math>A</math> contains the group <math>H</math> generated by <math>B</math>. 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 <math>B</math>, whether it is a member of <math>G</math>.
-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.
+* [[Normality testing problem]]: Given generating sets <math>A</math> for <math>G</math> and <math>B</math> for <math>H</math>, the problem asks whether <math>H</math> is a [[normal subgroup]] of <math>G</math>. 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 <math>B</math> by an element in <math>A</math> must be in <math>B</math>.
-===NP===
+* [[Normal closure-finding]]: This is solved using the normality testing problem
-The problem of checking membership in the subgroup is in nondeterministic polynomial-time. In other words, if <math>g \in H</math>, one can give a short proof of the fact, by constructing a circuit for outputting <math>g</math> as an expression in the elements of <math>B</math>. 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 <math>n</math>, we can argue that that circuit can be constructed and checked (nondeterministcally) in polynomial time.
+* [[Subnormality testing problem]]: This is solved using the normal closure-finding algorithm
-{{proofat|[[Membership testing is in NP]]}}
+==Algorithms==
-===co-AM===
+===Black-box group algorithms===
-The idea here is very similar to the general idea of showing that [[graph isomorphism]] is in co-AM.
+These work for a group specified by means of an [[encoding of a group|encoding]].
-==Permutation groups avatar==
+{| class="sortable" border="1"
+! Algorithm !! Additional information needed for algorithm, if any !! Time taken, where <math>N</math> is the order of the group and <math>s</math> is the size of the generating set !! Type of algorithm
+|-
+| [[Black-box group algorithm for finding the subgroup generated by a subset]]  || || <math>O(Ns)</math> times the time for the group operations. || deterministic
+|-
+| [[Nondeterministic black-box group algorithm for membership testing]] || || || nondeterministic
+|}
-In the situation where <math>G</math> 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 <math>\log N</math>, we actually have a way of using a generating set to obtain a membership test.
+===Permutation group algorithms===
-Refer [[Membership testing problem (old)]] for details as of now (they'll be put up here shortly).
+* [[Permutation group algorithm for membership testing]]
-==Linear groups avatar==
+===Linear group algorithms===
+* [[Linear group algorithm for membership testing]]