We show that the permutation group membership problem can be solved in depth (logn)3 on a Monte Carlo Boolean circuit of polynomial size in the restricted case in which the group is abelian. We also show that this restricted problem is NC1-hard for NSPACE(logn).
['Pierre McKenzie', 'Stephen A. Cook']
The parallel complexity of the abelian permutation group membership problem