Parallel algorithms for solvable permutation groups

摘要

A number of basic problems involving solvable and nilpotent permutation groups are shown to have fast parallel solutions. Testing solvability is in NC as well as, for solvable groups, finding order, testing membership, finding centralizers, finding centers, finding the derived series and finding a composition series. Additionally, for nilpotent groups, one can, in NC, find a central composition series, and find pointwise stabilizers of sets. The latter is applied to an instance of graph isomorphism. A useful tool is the observation that the problem of finding the smallest subspace containing a given set of vectors and closed under a given set of linear transformations (all over a small field) belongs to NC.