ECCC-Report TR04-109https://eccc.weizmann.ac.il/report/2004/109Comments and Revisions published for TR04-109en-usSat, 27 Nov 2004 21:42:56 +0200
Paper TR04-109
| On the Ring Isomorphism & Automorphism Problems |
Neeraj Kayal,
Nitin Saxena
https://eccc.weizmann.ac.il/report/2004/109We 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.
Sat, 27 Nov 2004 21:42:56 +0200https://eccc.weizmann.ac.il/report/2004/109