Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-109 | 15th November 2004 00:00

On the Ring Isomorphism & Automorphism Problems

RSS-Feed




TR04-109
Authors: Neeraj Kayal, Nitin Saxena
Publication: 27th November 2004 21:42
Downloads: 4821
Keywords: 


Abstract:

We study the complexity of the isomorphism and automorphism problems for finite rings with unity.

We show that both integer factorization and graph isomorphism reduce to the problem of counting
automorphisms of rings. The problem is shown to be in the complexity class $\AM \cap co\AM$
and hence is not $\NP$-complete unless the polynomial hierarchy collapses. Integer factorization
also reduces to the problem of finding nontrivial automorphism of a ring and to the problem of
finding isomorphism between two rings.

We also show that deciding whether a given ring has a non-trivial automorphism can be done in
deterministic polynomial time.



ISSN 1433-8092 | Imprint