Parallel algorithms for solvable permutation groups (Q1111023): Difference between revisions

Here is an elaborated extension of a recently published work [the second author and \textit{St. A. Cook}, SIAM J. Comput. 16, 880-909 (1987; Zbl 0647.68045)] on the complexity of algorithms for decisions with permutation groups and for deriving of interesting subgroups thereof. Considered are (again) groups defined by a finite list of generating permutations on a carrier (set of points) of given finite degree n: For the class of soluble groups existence and outline of fast parallel algorithms are proved/presented which handle tests for solubility, and for membership, computation of order, centralizer, center, (derived) series of commutator subgroups, composition series, and some more for the subclass of nilpotent groups. An application to automorphism groups of a certain class of vertex- coloured graphs is shown as of the same fastness (i.e., belonging into the earlier defined class NC). The main tool is the power commutator basis (PCB) defined and existing exactly for soluble groups G: \(g\in G\) iff \(g=\prod b_ i^{\epsilon_ i}\) with \(1\leq i\leq m\), \(b_ i\in G\), \(0\leq \epsilon_ i<\rho_ i>1\), whereby the subgroups \(<b_ i,...,b_ m>\) constitute a subnormal series, and \(ord(G)=\prod \rho_ i.\) The basis for the derivations of the complexity for the proposed problems is a lemma on the complexity for the computation of a linear base of all the products of a fixed finite set of linear transformations (including identity) of the space \({\mathbb{Z}}_ p^{\times d}\) (with prime p) which is shown to belong to class NC by recourse to some mentioned earlier results concerning linear algebra.