Name
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. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/CCC.2005.22 | CCC '05 Proceedings of the 20th Annual IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
integer factorization,automorphism problem,non-trivial automorphism,nontrivial automorphism,complexity class,deterministic polynomial time,finite ring,polynomial hierarchy collapse,Automorphism Problems,Ring Isomorphism | Graph automorphism,Discrete mathematics,Combinatorics,Group isomorphism,Graph isomorphism,Automorphism,Induced subgraph isomorphism problem,Isomorphism,Inner automorphism,Graph isomorphism problem,Mathematics | Journal |
Issue | ISSN | ISBN |
109 | 1093-0159 | 0-7695-2364-1 |
Citations | PageRank | References |
3 | 0.51 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Nitin Saxena | 2 | 280 | 26.72 |