Probabilistic Algorithms in Group Theory.
Abstract
A finite group G is commonly presented by a set of elements which generate G. The author argues that for algorithmic purposes a considerably better presentation for a fixed group G is given by random generator set for G: a set of random elements which generate G. He bounds the expected number of random elements required to generate a given group G. The main results are probabilistic algorithms which take as inputs a random generator set of fixed permutating group G is included in S sub n. Given are O(n to the 3rd power log n) inclusion and equality. Our bounds hold for any worse case input groups; we average only over the random generators representing the groups. Our algorithms are two orders of magnitude faster than the best previous algorithms for these group theoretic problems, which required omega(n to the 5th power) time even if given random generators. Furthermore, we show that in the case the input group is a 2-group with a random presentation, than those group theoretic problems can be solved by a parallel RAM in o(log n)to the third power expected time using n sub o(1) processors. Additional keywords: group membership testing; parallel algorithms. (Author).
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1984
- Accession Number
- ADA152253
Entities
People
- J. H. Reif
Organizations
- Harvard University