Answers are grounded in this paper and cite their sources.
We classify Abelian permutation group problems with respect to their parallel complexity. For such groups specified by generating permutations we show that testing membership, computing order and testing isomorphism are NC¹-equivalent to (and therefore have essentially the same parallel complexity as) determining solvability of a system of linear equations modulo a product of small prime powers; we show that intersecting two such groups is NC¹-equivalent to computing setwise stabilizers; we show that each of these problems is NC¹-reducible to the problem of computing a generator-relator presentation. Then we prove that the aforementioned problems belong to NC³, thus identifying several natural set recognition problems in $NC$ which may lie outside NC². Finally we prove that NC⁴ contains the problem of computing the cyclic decomposition of an Abelian permutation group. Background results include an NC¹ solution to the problem of computing the product of n integers modulo a log n-bit integer, and an NC¹ reduction from the problem of computing a path between two nodes in a graph to that of determining accessibility of one node from another.
No takes yet. Share an insight, caveat, or question.
McKenzie et al. (1987) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: