The parallel complexity of abelian permutation group problems. (English) Zbl 0647.68045

For solving group problems by computation it may be advantageous to consider the groups as permutation groups: the complexity will become a function of their degree, i.e. the cardinality n of the carrierset (which the group elements are operating on as permutations) whereas the order of such a group (the number of its elements) may be exponentially larger than n.
Considered is the class of finite Abelian groups, given by a finite list of generating elements represented as permutations on a carrier with given degree n. For several problems of general interest in this class the complexities of their computational solution are investigated with respect to parallel processing.
The aim is to show that these problems belong to classes NC k of functions, “superfast” computable on a net of parallel computers of “feasible” sizes (with investment polynomial in n for size, in (log n) k for depth).
The definition of NC and the derivations rely on properties of so called uniform Boolean circuits defined elsewhere.
By suitable formulation of the envisaged problems the main parts of their solution are arranged in steps with application of the same process to each generator, each power thereof, each divisor of the degree etc. so that the application can be done in parallel manner and the overall process requires investment of polynomial order with limited degree: it is shown, that the problems “belong” to NC k, where \(k=1,2,3\), or 4 depending on problem class - or are at least NC k-reducable to known often easier tractable problems.
Some of those problems take into account the structure of the embedding within the symmetry group of the permutations of the carrier, so that their results depend on the actual representation of the generators as permutations.
The classes cover testing for Abelian property, membership, isomorphism, computation of the group order, intersection of two groups, signature of Sylow decomposition. Also solutions are indicated for systems of linear congruences, congruences of products with not to much factors, and path finding (with minimal edge count) and connected problems for graphs from adjacency lists. Some of the results are marked for extension to larger (i.e. non-Abelian) classes of groups.
The needed basis apparatus of Abelian group theory is completely listed in neat conciseness, the relevant concepts of circuits, complexity, and parallelism require recourse to the quoted publications/reports.
Reviewer: K.G.Brokate


68Q25 Analysis of algorithms and problem complexity
20K01 Finite abelian groups
68W30 Symbolic computation and algebraic computation
20B35 Subgroups of symmetric groups
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
Full Text: DOI