caa a22 4500 467909652 CHVBK 20180406152846.0 cr unu---uuuuu 170328e20061201xx s 000 0 eng 10.1007/s00037-007-0219-8 doi (NATIONALLICENCE)springer-10.1007/s00037-007-0219-8 Complexity of Ring Morphism Problems [Elektronische Daten] [Neeraj Kayal, Nitin Saxena] 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. Birkhäuser Verlag, Basel, 2007 Ring nationallicence isomorphism nationallicence automorphism nationallicence polynomial hierarchy nationallicence graph isomorphism nationallicence integer factorization nationallicence 68Q15 nationallicence 13P99 nationallicence Kayal Neeraj Institute for Advanced Study, Einstein Drive, 08540, Princeton, NJ, USA aut Saxena Nitin Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands aut computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/4(2006-12-01), 342-390 1016-3328 15:4<342 2006 15 37 https://doi.org/10.1007/s00037-007-0219-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00037-007-0219-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Kayal Neeraj Institute for Advanced Study, Einstein Drive, 08540, Princeton, NJ, USA aut NATIONALLICENCE 700 1- Saxena Nitin Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ, Amsterdam, The Netherlands aut NATIONALLICENCE 773 0- computational complexity Birkhäuser-Verlag; www.birkhäuser.ch 15/4(2006-12-01), 342-390 1016-3328 15:4<342 2006 15 37 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer