Complexity of Ring Morphism Problems

We study the complexity of the isomorphism and automorphism problems for finite rings. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of a ring. This counting problem is shown to be in the functional version of the complexity class AM ∩ coAM and hence is not NP-complete unless the polynomial hierarchy collapses. As a “positive” result we show that deciding whether a given ring has a non-trivial automorphism can be done in deterministic polynomial time. Finding such an automorphism is, however, shown to be randomly equivalent to integer factorization.

Authors and Affiliations

1. Institute for Advanced Study, Einstein Drive, Princeton, NJ, 08540, USA

   Neeraj Kayal

2. Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands

   Nitin Saxena

Corresponding author

Correspondence to Neeraj Kayal.

Manuscript received 14 September 2005

Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.

Reprints and permissions