Computing in general Abelian groups is hard

DOI10.1016/0304-3975(85)90061-1MaRDI QIDQ1070820zbMATH OpenOpenAlexFDO

Authors Costas S. Iliopoulos

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90061-1

zbMATH Keywords

cyclicitycanonical structuregeneratorsprime factorizationprimality testingorder of an elementrelative complexitygroup-theoretic complexitymembership testingPolynomial time reductionsset of defining relations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Generators, relations, and presentations of groups (20F05) Primes (11A41) Finite abelian groups (20K01) Software, source code, etc. for problems pertaining to number theory (11-04)

Recommendations

• Analysis of algorithms on problems in general abelian groups
• scientific article; zbMATH DE number 1257081
• The Parallel Complexity of Abelian Permutation Group Problems
• On some computational problems in finite abelian groups
• An \(O(n)\) algorithm for Abelian \(p\)-group isomorphism and an \(O(n \log n)\) algorithm for Abelian group isomorphism

Cites work

• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3563269 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3443813 (Why is no real title available?)
• scientific article; zbMATH DE number 3353398 (Why is no real title available?)
• Analysis of algorithms on problems in general abelian groups
• Factorization and Primality Tests
• Fast multiplication of large numbers
• Group-theoretic algorithms and graph isomorphism
• On distinguishing prime numbers from composite numbers
• On the computational power of pushdown automata
• Riemann's hypothesis and tests for primality
• The distribution of quadratic residues and non‐residues
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix

Cited in

(10)

• Generation of finite groups with cyclic Sylow subgroups
• On the computational complexity of the Abelian permutation group structure, membership and intersection problems
• Algorithms for computing parameters of graph-based extensions of BCH codes
• On the complexity of some problems on groups input as multiplication tables
• Collection from the left and other strategies
• scientific article; zbMATH DE number 5263286 (Why is no real title available?)
• scientific article; zbMATH DE number 3970736 (Why is no real title available?)
• Analysis of algorithms on problems in general abelian groups
• Computing a basis for a finite Abelian p-group
• Algorithms for group isomorphism via group extensions and cohomology

This page was built for publication: Computing in general Abelian groups is hard

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