The parallel complexity of the abelian permutation group membership problem
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 154-161
- https://doi.org/10.1109/sfcs.1983.74
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
This publication has 13 references indexed in Scilit:
- The classification of problems which have fast parallel algorithmsLecture Notes in Computer Science, 1983
- Fast parallel matrix and GCD computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A compact representation for permutation groupsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- The maximum flow problem is log space complete for PTheoretical Computer Science, 1982
- Group-Theoretic Algorithms and Graph IsomorphismLecture Notes in Computer Science, 1982
- Tree-size bounded alternationJournal of Computer and System Sciences, 1980
- On simultaneous resource boundsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Linear programming is log-space hard for PInformation Processing Letters, 1979
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- The circuit value problem is log space complete for PACM SIGACT News, 1975