Under the auspices of the Computational Complexity Foundation (CCF)
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.