Affordable Access

Publisher Website

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
  • Computer Science

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.