Research Initiation Award: The Computational Complexity of Circuit Isomorphism

研究启动奖：电路同构的计算复杂性

• 批准号: 9309137
• 负责人: Richard Chang
• 金额: $ 5.67万
• 依托单位: University of Maryland Baltimore County
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-08-15 至 1997-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9309137&HistoricalAwards=false
• 关键词: Research; Initiation; Award; Computational; Complexity

The Circuit Isomorphism problem is the problem of deciding whether two given circuits are isomorphic. Two circuits are isomorphic, in this sense, when they are functionally identical (compute the same input/output relation) under some permutation of the input values. The computational complexity of this problem has not been established. This project undertakes a comprehensive study of the complexity of Circuit Isomorphism in relation to the standard complexity classes. It is conjectured that Circuit Isomorphism is an incomplete problem in the Polynomial Hierarchy. The basis of this conjecture relies on the observation that the counting version of the Circuit Isomorphism problem has a relatively lower computational complexity. (The counting version of the Circuit Isomorphism problem asks for the number of permutations which certify the isomorphism between the two circuits.) Thus, it seems appropriate for the decision problem to have a lower computational complexity as well. Extensive comparisons are made to the much better studied Graph Isomorphism problem, which is a special case of the Circuit Isomorphism problem. The results of this study would bring about a better understanding of the computational complexity of Circuit Isomorphism and establish a new link between counting problems and decision problems.

电路同构问题是判定两个给定电路是否同构的问题。 两个电路是同构的，在这个意义上，当它们在输入值的某种排列下功能相同（计算相同的输入/输出关系）时。 该问题的计算复杂性尚未确定。 这个项目全面研究了电路同构的复杂性与标准复杂性类的关系。 证明了电路同构是多项式族中的一个不完全问题。 这个猜想的基础依赖于观察到的计数版本的电路同构问题具有相对较低的计算复杂度。 (The电路同构问题的计数版本要求证明两个电路之间同构的排列的数量。 因此，决策问题具有较低的计算复杂度似乎也是合适的。 广泛的比较，更好地研究图同构问题，这是一个特殊情况下的电路同构问题。 本文的研究结果将有助于更好地理解电路同构的计算复杂性，并在计数问题和决策问题之间建立新的联系。