Title :
The parallel complexity of the abelian permutation group membership problem
Author :
Mckenzie, Pierre ; Cook, Stephen A.
Abstract :
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).
Keywords :
Circuits; Computer science; Concurrent computing; Councils; Linear programming; Monte Carlo methods; Parallel algorithms; Polynomials; Testing; Voting;
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-8186-0508-1
DOI :
10.1109/SFCS.1983.74
