Name
Abstract | ||
|---|---|---|
This paper considers "black box groups," i.e., finite groups whose elements are uniquely encoded by strings of uniform length, with group operations being performed by a group oracle B. Let G, H be such groups, each given by a list of generators. It is known that the problem of membership in G belongs to NP(B) [L. Babai and E. Szemeredi, Proceedings of the 25th IEEE Symposium on the Foundation of Computer Science, 1984, pp. 229-240]. The following problems are shown to belong to the complexity class AM(B); i.e., they possess bounded-round randomized interactive proofs (Arthur-Merlin protocols): nonmembership in G, the verification of the order of G, isomorphism of G and H, and checking the list of composition factors of G. A group oracle B is constructed, under which none of these problems belongs to NP(B), even for abelian groups.All the results extend to "black box factor groups," i.e., groups defined as factor groups G/N, where G is a black box group, N left-pointing open triangle G is a normal subgroup, and both G and N are given by lists of generators.A list of consequences puts verification of a large number of basic group theoretic constructions in (AM intersection of coAM)B. These include homomorphisms, kernels, intersection of subgroups and cosets, membership in double cosets, centralizers, the center, cores, minimal normal subgroups, and the maximal solvable normal subgroup. A notable extension of the applicability of the results is obtained by observing that subgroups of the automorphism group of a black box group G (given by a list of generators in their action on the generators of G) can be viewed (in a nondeterministic setting) as black box groups themselves.The results are applicable to matrix groups over finite fields and to factor groups thereof. (Matrix operations replace the group oracle.) In this case, most problems listed are conjectured to belong to NP, but a proposed approach to the proof of this statement requires detailed knowledge of the classification of finite simple groups. In contrast, the material presented here relies on the elements of group theory only (with the exception of the composition factors result). These applications provided the original motivation for introducing the Arthur-Merlin protocols in [L. Babai, Proceedings of the 17th Annual ACM Symposium on the Theory of Computing, 1985, pp. 421-429], where some of the results of this paper were announced.The key to the basic results is a "local expansion lemma" for groups, which has since found applications in designing polynomial time algorithms. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1137/0405008 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
interactive proof,bounded round,finite group,expansion,group,complexity,randomization | Black box (phreaking),Complexity class,Discrete mathematics,Abelian group,Combinatorics,Upper and lower bounds,Turing machine,Isomorphism,Finite group,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
5 | 1 | 0895-4801 |
Citations | PageRank | References |
26 | 2.11 | 10 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laszlo Babai | 1 | 3537 | 573.58 |