L. Babai
ABSTRACT
We show that the basic problems of permutation group manipulation admit efficient parallel solutions. Given a permutation group G by a list of generators, we find a set of NC-efficient strong generators in NC. Using this, we show, that the following problems are in NC: membership in G; determining the order of G; finding the center of G; finding a composition series of G along with permutation representations of each composition factor. Moreover, given G, we are able to find the pointwise stabilizer of a set in NC. One consequence is that isomorphism of graphs with bounded multiplicity of eigenvalues is in NC.
The analysis of the algorithms depends, in several ways, on consequences of the classification of finite simple groups.
- Ba79.Bahai, L., Monte Carlo algor4thms ~ graph ~ornorph~m tezt~ng, Tech. Rep. 79-10, D~p. Math. et Star., Univ. de Montr4al, 1979.Google Scholar
- Ba86.L. Babai, A Lag Vegaz-NC algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues, Proc. 27th IEEE FOCS, 1986, 303-312.Google ScholarDigital Library
- BGM.L. Babel, D.Yu. Grigoryev and D.M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proc. 14th ACM STOC, 1982, 310-324. Google ScholarDigital Library
- BKL.L. Babel, W.M. Kantor and E.M. Luks, Computational and the classificatio~ of finite simple groups, Proc. 24th FOCS, 1983, 162-171.Google Scholar
- BLS.L. Bahai, E.M. Luks and //,. Seress, Mar~aging permutation groups in O(n4 log~ n) time, in prepar~ lionGoogle Scholar
- BS1.L. Babel and ~. Seress, On the degree of transitivity of permutation groups' a short proof, J. Combinatorial Theory-A, to appearGoogle Scholar
- BS2.L. Babel and .~. Seress, On the diameter of Cayley graphs of the symmetric group, manuscriptGoogle Scholar
- BSz.L. Babel and E. Szemer~di, On the complexity of matrix group problems, Proc. 24th IEEE FOCS, 1984, 229-240.Google Scholar
- Bo.R.C. Bose, Strongly regular graphs, partial geomtriesj and partially balanced desig~.sj Pacific J. Math. 13 (1963), 389-419.Google Scholar
- Cam.P.J. Cameron, Finite perrnutatior~ groups and finite simple groups, Bull. London Math. Soc. 11 (x079), 16i-~60.Google Scholar
- Car.R. Carter, Simple groups of Lie type, Wiley, London 1972Google Scholar
- Ca.S.A. Cook, The classification of problems which have fast parallel algorithms, Proc. Conf. FCT'83, Lecture Notes in Comp. Sci. 158, Springer 1983, 78- 93. Google ScholarDigital Library
- CKS.C.W. Curtis, W.M. Kantor and G.L. Seitz, The ~-transitive permutation representations of the finite Che~alley groups, Trans. A.M.S. 2:18 (1976), 1-57.Google Scholar
- De.P. Delsarte (1973), An algebraic approach to the association schemes of coding theory"~ Philips Res. Rept. Suppl. 10 (1973).Google Scholar
- FHL.M.L. Furst, J. Hopcroft and E.M. Luks, Polynomial time algorithms for permutation groups, Proc. 21th IEEE FOCS, 1980, 36-41.Google ScholarDigital Library
- vzGS.J. yon zur Gathen and G. Seroussi, Boolean circuits versus arithmetic circuits, Proc. 6th Intl. Conf. Comp. Sci., Santiago, Chile, 1986, 171-184.Google Scholar
- Go.D. Gorenstein, Finite Mmpl~ groups and their classification, Academic Press, 1986Google Scholar
- Ha.M. Hall, Jr., The Theory of Groups, Macmillan, New York 1959.Google Scholar
- HW.G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 5th ed., Clarendon Press 1979.Google Scholar
- Jo.C. Jordan, Nou~ellcs rechcrches st, r la limite de transitivitd des groupes qui ne contiennent pat le groupe alterni, ~ourn. de Math~matiques (5) I (1895), 35-60.Google Scholar
- Ka1.W.M. Kantor, Permutation representations of the finite classical groups of small degree or rank, J. Algebra 60 (1979), 158-168.Google ScholarCross Ref
- Ka2.W.M. Kantor, S~iow's theorem in polynomial time, J. Comp. Sys. Sci. 30 (1985), 359-394.Google ScholarCross Ref
- Lu82.E.M. Luks, Isomorphism o/grcpks of bouttded valence car~ be tested in polynomial time, J. Comp. Sys. Sci. 25 (1982), 42-65.Google ScholarCross Ref
- Lu86.E.M. Luks, Parallel algorithms for pertnutation groups and graph isomorphism, Proc. 27th iEEE FOCS, 1986, 292-302.Google ScholarDigital Library
- Lu87.E.M. Luks, Computing the composition factors of a permutation group in polynomial time, Combinatorica 7 (1987), 87-99. Google ScholarDigital Library
- LM.E.M. Luks and P. McKenzie, Fast parallel computation with permutation groups, Proc. 26th IEEE Focs, 50~-5~4. Google ScholarDigital Library
- MS.M.$. Slo~,e (~078), The Theory of Error-correcting Codes, North-Holland, Amsterdam 1978.Google Scholar
- MC.P. McKen~ie and S.A. Cook, The parallel complexity of the abelian permutation group membership problem, Proc. 24th IEEE FOCS, 1983, 154-161.Google Scholar
- Mu.K. Muhnuley, A fast parallel algorithm to comp~tte the rar~k of a matrix over an arbitrary field, Combinatorica 7 (1987), 101-104. Google ScholarDigital Library
- Pi.N. Pippenger, On simultaneous resource bour~ds, Proc. 20th IEEE FOCS, 1979, 307-311.Google ScholarDigital Library
- Sc.L.L. Scott, Representations in characteristic p, in: Proc. Santa Cruz Conf. on Finite Groups, A.M.S. 1980, 319-322.Google Scholar
- Si67.C.C. Sims, Graphs and finite permutatior~ groups, Math. Z. 95 (1967), 76-86.Google ScholarCross Ref
- Si70.C.C. Sims, Computatiogal methods in the stud~ of permutation froups, in: Computational Problems in Abstract, Algebra, J. Leech, ed., Pergamon Press 1970, 169-183.Google Scholar
- Wi.H. Wielandt, Finite Permutation Groups, Acad. Press, N.Y. 1964.Google Scholar
Index Terms
- Permutation groups in NC
Recommendations
Permutation Groups, Vertex-transitive Digraphs and Semiregular Automorphisms
A nonidentity element of a permutation group is said to be semiregular if all of its orbits have the same length. The work in this paper is linked to 6 where the problem of existence of semiregular automorphisms in vertex-transitive digraphs was posed. ...
On the permutation groups of cyclic codes
We classify the permutation groups of cyclic codes over a finite field. As a special case, we find the permutation groups of non-primitive BCH codes of prime length. In addition, the Sylow p-subgroup of the permutation group is given for many cyclic ...
Transitive Permutation Groups of Prime-Squared Degree
We explicitly determine all of the transitive groups of degree i>p2, i>p a prime, whose Sylow i>p-subgroup is not isomorphic to the wreath product {\Bbb Z}_p\wr{\Bbb Z}_p . Furthermore, we provide a general description of the transitive groups ...
Comments