Membership testing problem: Difference between revisions

Revision as of 19:14, 25 June 2013

Description

Given data

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

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 7: / Line 7: @@
 ===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===
+==Algorithms==
-We let <math>N</math> denote the order 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>.
+===Black-box group algorithms===
-All complexities will be measured in terms of <math>n = \log N</math>.
+These work for a group specified by means of an [[encoding of a group|encoding]].
-==Black-box 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
+|}
-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.
+===Permutation group algorithms===
-===NP===
+* [[Permutation group algorithm for membership testing]]
-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.
+===Linear group algorithms===
-{{proofat|[[Membership testing is in NP]]}}
+* [[Linear group algorithm for membership testing]]
-===co-AM===
-The idea here is very similar to the general idea of showing that [[graph isomorphism]] is in co-AM.
-{{proofat|[[Membership testing is in co-AM]]}}
-==Permutation groups avatar==
-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.
-Refer [[Membership testing problem (old)]] for details as of now (they'll be put up here shortly).
-==Linear groups avatar==