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.
