The Parallel Complexity of Abelian Permutation Group Problems
Pierre McKenzie, Stephen A Cook · SIAM Journal on Computing · 1987
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^1 $-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^1 $-equivalent to computing setwise stabilizers; we show that each of these problems is $NC^1 $-reducible to the problem of computing a generator-relator presentation. Then we prove that the aforementioned problems belong to $NC^3 $, thus identifying several natural set recognition problems in $NC$ which may lie outside $NC^2 $. Finally we prove that $NC^4 $ contains the problem of computing the cyclic decomposition of an Abelian permutation group. Background results include an $NC^1 $ solution to the problem of computing the product of n integers modulo a $\lceil {\log n} \rceil $-bit integer, and an $NC^1 $ reduction from the problem of computing a path between two nodes in a graph to that of determining accessibility of one node from another.