Permutation groups in NC

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.

REFERENCES

• Ba79: Bahai, L., Monte Carlo algor4thms ~ graph ~ornorph~m tezt~ng, Tech. Rep. 79-10, D~p. Math. et Star., Univ. de Montr4al, 1979.
• Ba86: L. Babai, A Lag Vegaz-NC algorithm for isomorphism of graphs with bounded multiplicity of eigenvalues, Proc. 27th IEEE FOCS, 1986, 303-312.
• BGM: László Babai , D. Yu. Grigoryev , David M. Mount, Isomorphism of graphs with bounded eigenvalue multiplicity, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.310-324, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802206]
• BKL: L. Babel, W.M. Kantor and E.M. Luks, Computational and the classificatio~ of finite simple groups, Proc. 24th FOCS, 1983, 162-171.
• BLS: L. Bahai, E.M. Luks and //,. Seress, Mar~aging permutation groups in O(n4 log~ n) time, in prepar~ lion
• BS1: L. Babel and ~. Seress, On the degree of transitivity of permutation groups' a short proof, J. Combinatorial Theory-A, to appear
• BS2: L. Babel and .~. Seress, On the diameter of Cayley graphs of the symmetric group, manuscript
• BSz: L. Babel and E. Szemer~di, On the complexity of matrix group problems, Proc. 24th IEEE FOCS, 1984, 229-240.
• Bo: R.C. Bose, Strongly regular graphs, partial geomtriesj and partially balanced desig~.sj Pacific J. Math. 13 (1963), 389-419.
• Cam: P.J. Cameron, Finite perrnutatior~ groups and finite simple groups, Bull. London Math. Soc. 11 (x079), 16i-~60.
• Car: R. Carter, Simple groups of Lie type, Wiley, London 1972
• Ca: Stephen A. Cook, The Classifikation of Problems which have Fast Parallel Algorithms, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.78-93, August 21-27, 1983
• 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.
• De: P. Delsarte (1973), An algebraic approach to the association schemes of coding theory"~ Philips Res. Rept. Suppl. 10 (1973).
• FHL: M.L. Furst, J. Hopcroft and E.M. Luks, Polynomial time algorithms for permutation groups, Proc. 21th IEEE FOCS, 1980, 36-41.
• vzGS: J. yon zur Gathen and G. Seroussi, Boolean circuits versus arithmetic circuits, Proc. 6th Intl. Conf. Comp. Sci., Santiago, Chile, 1986, 171-184.
• Go: D. Gorenstein, Finite Mmpl~ groups and their classification, Academic Press, 1986
• Ha: M. Hall, Jr., The Theory of Groups, Macmillan, New York 1959.
• HW: G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, 5th ed., Clarendon Press 1979.
• 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.
• Ka1: W.M. Kantor, Permutation representations of the finite classical groups of small degree or rank, J. Algebra 60 (1979), 158-168.
• Ka2: W.M. Kantor, S~iow's theorem in polynomial time, J. Comp. Sys. Sci. 30 (1985), 359-394.
• Lu82: E.M. Luks, Isomorphism o/grcpks of bouttded valence car~ be tested in polynomial time, J. Comp. Sys. Sci. 25 (1982), 42-65.
• Lu86: E.M. Luks, Parallel algorithms for pertnutation groups and graph isomorphism, Proc. 27th iEEE FOCS, 1986, 292-302.
• Lu87: E. M. Luks, Computing the composition factors of a permutation group in polynomial time, Combinatorica, v.7 n.1, p.87-99, Jan. 1987 [doi>10.1007/BF02579204]
• LM: E.M. Luks and P. McKenzie, Fast parallel computation with permutation groups, Proc. 26th IEEE Focs, 50~-5~4.
• MS: M.$. Slo~,e (~078), The Theory of Error-correcting Codes, North-Holland, Amsterdam 1978.
• 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.
• Mu: K. Mulmuley, A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Combinatorica, v.7 n.1, p.101-104, Jan. 1987 [doi>10.1007/BF02579205]
• Pi: N. Pippenger, On simultaneous resource bour~ds, Proc. 20th IEEE FOCS, 1979, 307-311.
• Sc: L.L. Scott, Representations in characteristic p, in: Proc. Santa Cruz Conf. on Finite Groups, A.M.S. 1980, 319-322.
• Si67: C.C. Sims, Graphs and finite permutatior~ groups, Math. Z. 95 (1967), 76-86.
• 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.
• Wi: H. Wielandt, Finite Permutation Groups, Acad. Press, N.Y. 1964.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Theory, Verification