Name
Abstract | ||
|---|---|---|
We study the complexity of the isomorphism and automorphism problems for finite rings. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of a ring. This counting problem is shown to be in the functional version of the complexity class AM 驴 coAM and hence is not NP-complete unless the polynomial hierarchy collapses. As a "positive" result we show that deciding whether a given ring has a non-trivial automorphism can be done in deterministic polynomial time. Finding such an automorphism is, however, shown to be randomly equivalent to integer factorization. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/s00037-007-0219-8 | Computational Complexity |
Keywords | Field | DocType |
graph isomorphism,integer factorization,ring,isomorphism,automorphism,complexity class,polynomial time | Graph automorphism,Discrete mathematics,Combinatorics,Group isomorphism,Graph isomorphism,Automorphism,P versus NP problem,UP,Inner automorphism,Factorization of polynomials,Mathematics | Journal |
Volume | Issue | ISSN |
15 | 4 | 1016-3328 |
Citations | PageRank | References |
3 | 0.46 | 11 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeraj Kayal | 1 | 263 | 19.39 |
| Nitin Saxena | 2 | 280 | 26.72 |