Kayal, N. ; Saxena, N. (2005) On the Ring Isomorphism and Automorphism Problems In: CCC '05: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, June 2005.
Full text not available from this repository.
Official URL: http://doi.org/10.1109/CCC.2005.22
Related URL: http://dx.doi.org/10.1109/CCC.2005.22
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 coAM 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.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Association for Computing Machinery. |
| ID Code: | 122782 |
| Deposited On: | 16 Aug 2021 08:21 |
| Last Modified: | 16 Aug 2021 08:21 |
Repository Staff Only: item control page
