The Parallel Complexity of Abelian Permutation Group Problems

DOI10.1137/0216058zbMath0647.68045OpenAlexW2080772479MaRDI QIDQ3792240

Pierre McKenzie, Stephen A. Cook

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216058

zbMATH Keywords

finite Abelian groupsparallel complexityparallel processingintersection of permutation groupsoptimal paths in graphsrepresentation of generators as permutations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite abelian groups (20K01) Subgroups of symmetric groups (20B35)

Related Items (8)

On the parallel complexity of linear groups ⋮ Membership testing in commutative transformation semigroups ⋮ Parallel algorithms for solvable permutation groups ⋮ The complexity of intersecting finite automata having few final states ⋮ An \(NC^ 2\) algorithm for testing similarity of matrices ⋮ The parallel complexity of graph canonization under abelian group action ⋮ Uniform derandomization from pathetic lower bounds ⋮ Testing membership: Beyond permutation groups

This page was built for publication: The Parallel Complexity of Abelian Permutation Group Problems