# Computing in general abelian groups is hard

- Authors
- Journal
- Theoretical Computer Science 0304-3975
- Publisher
- Elsevier
- Publication Date
- Volume
- 41
- Identifiers
- DOI: 10.1016/0304-3975(85)90061-1
- Disciplines

## Abstract

Abstract The relative complexity of the following problems on abelian groups represented by an explicit set of generators is investigated: (i) computing a set of defining relations, (ii) computing the order of an element, (iii) membership testing, (iv) testing whether or not a group is cyclic, (v) computing the canonical structure of an abelian group. Polynomial time reductions among the above problems are established. Moreover the problem of ‘prime factorization’ is shown to be polynomial time reducible to the problems (i), (ii), (iii), and (v) and ‘primality testing’ is shown to be polynomial time reducible to the problem (iv). Therefore, the group-theoretic problems above are computationally harder than factorization and primality testing.

## There are no comments yet on this publication. Be the first to share your thoughts.