Research Initiation Award: The Computational Complexity of Circuit Isomorphism

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

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.