Computing the composition factors of a permutation group in polynomial time
The paper gives a proof that the composition factors of a permutation group G of degree n can be computed from a given set of generators in time polynomial in n, a result that had previously been announced and sketched by the author [\textit{E. M. Luks}, J. Comput. Syst. Sci. 25, 42-65 (1982; Zbl 0493.68064); \textit{L. Babai}, \textit{W. M. Kantor}, \textit{E. M. Luks}, Computational complexity and the classification of finite simple groups, Proc. 24th IEEE Symp. Found. Comput. Sci., 162-171 (1983)]. As this author states explicitly, he restricts attention to the issue of polynomial time without disgressing to optimize the time bounds. So also the question, for which size of groups the algorithm lends itself to practical implementation and use is left undiscussed. This (in the reviewer's view) more important question has however meanwhile (a first draft of the paper under review was received 1981, the final version 1986) been the topic of several independent investigations, see in particular \textit{P. M. Neumann} [Groups, Proc. St. Andrews 1985, Lond. Math. Soc. Lect. Note Ser. 121, 59-92 (1986; Zbl 0612.20001)]. The present paper states briefly all needed prerequisites with careful references, as all these approaches it builds on the O'Nan-Scott classification of primitive permutation groups.
- An Algorithm for Finding the Blocks of a Permutation Group
- Finite Permutation Groups and Finite Simple Groups
- scientific article; zbMATH DE number 3722702 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3341276 (Why is no real title available?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Polynomial-time algorithms for finding elements of prime order and sylow subgroups
- Polynomial-time versions of Sylow's theorem
- Solvability of groups of odd order
- Sylow's theorem in polynomial time
- On the nilpotent Lie algebras of dimension \(\leq 7)\)
- Parallel algorithms for solvable permutation groups
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Finding composition factors of permutation groups of degree \(n\leq 10^ 6\)
- Algorithms for matrix groups and the Tits alternative
- On the degree of transitivity of permutation groups: A short proof
- Subcomplete generalizations of graph isomorphism
- Constructing composition factors for a linear group in polynomial time
- Isomorphism testing of groups of cube-free order
- Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
- scientific article; zbMATH DE number 1263311 (Why is no real title available?)
- scientific article; zbMATH DE number 475352 (Why is no real title available?)
- scientific article; zbMATH DE number 475362 (Why is no real title available?)
- Conjugacy classes in finite permutation groups via homomorphic images
- scientific article; zbMATH DE number 2151233 (Why is no real title available?)
- Formations of finite groups in polynomial time: \(\mathfrak{F}\)-residuals and \(\mathfrak{F}\)-subnormality
This page was built for publication: Computing the composition factors of a permutation group in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581532)
