Complexity of Ring Morphism Problems
Complexity of Ring Morphism Problems
复制标题
环态射问题的复杂性
DOI：
10.1007/s00037-007-0219-8
复制
发表时间：
2006
影响因子：
1.4
通讯作者：
Nitin Saxena
中科院分区：
文献类型：
--
作者：
N. Kayal;Nitin Saxena
摘要。我们研究有限环的同构和自动形态问题的复杂性。因此，除非多项式层次结构崩溃，否则coam coam and coam and coam and coam and coam and coam and coam。但是，可以在确定性的多项式时间内完成自动形态。
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.