## Abstract

A permutation group G may be concisely described by a set S of generators (\S\ need not be larger than log |G|). From such a short description, however, it is not immediately clear how to efficiently obtain various kinds of information about the group. Furst, Hopcroft, and Luks [FHL] showed that an algorithm of Sims [Si] for computing the order of G and performing membership tests runs in polynomial time. Sims's algorithm relies on combinatorial methods, and there is no deep group theory involved in the analysis. Polynomial time algorithms for determining various aspects of the structure of G are also known. However, it seems that algorithms which give us more information about G require increasing amounts of group theory for their analyses. An example is Luks's algorithm [Lu2] to find composition factors (the "building blocks" of G), which requires the classification of finite simple groups (CFSG) for its proof of correctness. Kantor's algorithm [Ka] for finding Sylow subgroups likewise requires CFSG. As the proof of CFSG is 15,000 manuscript pages long (according to Gorenstein [Go2]), it is reasonable to ask whether so much group theory is necessary to study the computational complexity of permutation group problems. We give a deterministic polynomial time algorithm to compute the composition factors of a permutation group, given by a set of generators. This is the first polynomial time algorithm for the composition factor problem with an analysis that does not depend on CFSG. In addition, we give a Monte Carlo version of our algorithm which runs in nearly linear (0(nlog^{c}n)) time for the class of "small-base" permutation groups introduced by Babai, Cooperman, Finkelstein, and Seress [BCFS]. This algorithm is significantly less complicated than other algorithms for the same problem, and should be easier to implement efficiently.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 |

Editors | Manuel Bronstein |

Publisher | Association for Computing Machinery |

Pages | 127-134 |

Number of pages | 8 |

ISBN (Electronic) | 0897916042 |

DOIs | |

State | Published - Aug 1 1993 |

Event | 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 - Kiev, Ukraine Duration: Jul 6 1993 → Jul 8 1993 |

### Publication series

Name | Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC |
---|

### Other

Other | 1993 International Symposium on Symbolic and Algebraic Computation, ISSAC 1993 |
---|---|

Country/Territory | Ukraine |

City | Kiev |

Period | 7/6/93 → 7/8/93 |

## All Science Journal Classification (ASJC) codes

- Mathematics(all)