The Parallel Complexity of Abelian Permutation Group Problems

DOI10.1137/0216058MaRDI QIDQ3792240zbMATH OpenOpenAlexFDO

Authors Pierre McKenzie, Stephen 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 groupsintersection of permutation groupsoptimal paths in graphsparallel complexityparallel processingrepresentation of generators as permutations

Mathematics Subject Classification ID

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

Recommendations

• On the computational complexity of the Abelian permutation group structure, membership and intersection problems
• Parallel algorithms for solvable permutation groups
• scientific article; zbMATH DE number 3931234
• scientific article; zbMATH DE number 18644
• scientific article; zbMATH DE number 4145340
• On the parallel complexity of linear groups
• scientific article; zbMATH DE number 475372
• Parallel complexity for nilpotent groups
• scientific article; zbMATH DE number 475362
• scientific article; zbMATH DE number 609987

Cited in

(23)

• Computing in general Abelian groups is hard
• On the computational complexity of the Abelian permutation group structure, membership and intersection problems
• Membership testing in commutative transformation semigroups
• Parallel algorithms for solvable permutation groups
• An NC^ 2 algorithm for testing similarity of matrices
• Monte Carlo circuits for the abelian permutation group intersection problem
• Uniform derandomization from pathetic lower bounds
• Canonizing hypergraphs under abelian group action
• The complexity of intersecting finite automata having few final states
• scientific article; zbMATH DE number 4145340 (Why is no real title available?)
• scientific article; zbMATH DE number 3931234 (Why is no real title available?)
• The parallel complexity of graph canonization under abelian group action
• scientific article; zbMATH DE number 4049036 (Why is no real title available?)
• scientific article; zbMATH DE number 18644 (Why is no real title available?)
• On the parallel complexity of linear groups
• scientific article; zbMATH DE number 841570 (Why is no real title available?)
• Testing membership: Beyond permutation groups
• Abelian logic gates
• A nonadaptive NC checker for permutation group intersection
• On homomorphic encryption using abelian groups: classical security analysis
• Robustness for space-bounded statistical zero knowledge
• Parameterized complexity of factorization problems
• The parallel dynamic complexity of the abelian Cayley group membership problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3792240)