Complexity of Ring Morphism Problems

Computational Complexity | , Vol 15: pp. 342-390

Invited to Special Issue of Computational Complexity Journal

Publication

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 \AMco\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.