Fast parallel computation with permutation groups
Authors:
- Eugene M. LuksELEugene M. Luks
- Pierre MckenziePMPierre Mckenzie
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 505-514
Abstract
We develop fast parallel solutions to a number of basic problems involving solvable and nilpotent permutation groups. Testing solvability is in NC, and RNC includes, for solvable groups, finding order, testing membership, finding the derived series and finding a composition series. Additionally, for nilpotent groups, one can, in RNC, find the center, a central composition series, and point-wise stabilizers of sets. There are applications to graph isomorphism. In fact, we exhibit a class of vertex-colored graphs for which determining isomorphism is NC-equivalent to computing ranks of matrices Over small fields. A useful tool is the observation that the problem of finding the smallest subspace containing a given set of vectors and closed under a given set of linear transformations (all over a small field) belongs to RNC.Keywords
This publication has 10 references indexed in Scilit:
- The parallel complexity of the abelian permutation group membership problem1983
- The classification of problems which have fast parallel algorithmsLecture Notes in Computer Science, 1983
- On the orders of primitive groups with restricted nonabelian composition factorsJournal of Algebra, 1982
- Fast parallel matrix and GCD computations1982
- Solvable and Nilpotent Subgroups of GL(n,qm)Canadian Journal of Mathematics, 1982
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- A polynomial bound for the orders of primitive solvable groupsJournal of Algebra, 1982
- Polynomial-time algorithms for permutation groups1980
- On simultaneous resource bounds1979
- Computational methods in the study of permutation groups††This research was supported in part by the National Science Foundation.1970