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.