6
$\begingroup$

Given two circuits, how hard is it to tell if they represent the same function? Clearly, this must be at least as easy as Graph Isomorphism since you can represent any circuit as a graph.

$\endgroup$
  • 2
    $\begingroup$ Nope. Two non-isomorphic circuits can have the same function. $\endgroup$ – Chad Brewbaker Jan 24 '14 at 22:06
  • 6
    $\begingroup$ It is easy to see that circuit isomorphism is coNP-complete by an immediate reduction from TAUTOLOGY: given a boolean formula $\varphi$ build the corresponding circuit C, and compare it to an always true circuit (e.g. $x \lor \bar{x}$). $\endgroup$ – Marzio De Biasi Jan 24 '14 at 22:14
  • $\begingroup$ the problem complexity seems to be related to CNF/DNF conversion at heart maybe... one can convert any circuit to either CNF or DNF for comparison by "multiplying out". it is easier with monotone circuits because the CNF/DNF representations are unique. $\endgroup$ – vzn Jan 24 '14 at 22:36
  • 7
    $\begingroup$ The problem you state is more typically known as Circuit Equivalence. Marzio is correct that Circuit Equivalence is coNP-complete. Circuit Isomorphism is the problem: given two circuits $C_1, C_2$ on $n$ inputs, is there a permutation $\pi \in S_n$ such that $C_1(\vec{x})$ and $C_2(\pi(\vec{x}))$ compute the same function? Circuit Isomorphism has a status similar to that of Graph Isomorphism, but one level higher in $\mathsf{PH}$: it is coNP-hard, not known to be in coNP, in $\mathsf{\Sigma_2 P}$, but not $\mathsf{\Sigma_2 P}$-complete unless $\mathsf{PH} = \mathsf{\Sigma_3 P}$. $\endgroup$ – Joshua Grochow Jan 25 '14 at 0:23
  • $\begingroup$ @JoshuaGrochow: right! I think you can convert the comment to an answer saying that circuit equivalence is coNP-complete by a direct reduction from TAUTOLOGY and mentioning that the definitions are also typically used with formulas (boolean equivalence/isomorphism ). $\endgroup$ – Marzio De Biasi Jan 25 '14 at 10:35
12
$\begingroup$

As pointed out by @Marzio De Biasi, the problem you are asking about is $\mathsf{coNP}$-complete, by a direct reduction from TAUTOLOGY: given a boolean formula $\varphi$, is $\varphi$ equivalent to the constant 1 circuit? It is easily seen to be in $\mathsf{coNP}$. (Given that Marzio really answered the question, I suggest anyone thinking of upvoting this answer flip a coin and if it lands heads then go vote for one of Marzio's other answers.)

Let me also clarify: the problem you are asking about is more typically called Circuit Equivalence. Circuit Isomorphism is the problem: given two circuits $C_1, C_2$ on $n$ inputs, is there a permutation $\pi \in S_n$ such that $C_1(\vec{x})$ and $C_2(\pi(\vec{x}))$ are equivalent? Circuit Isomorphism has a status similar to that of Graph Isomorphism, but one level higher in $\mathsf{PH}$: it is $\mathsf{coNP}$-hard (by the same reduction above), not known to be in $\mathsf{coNP}$, in $\mathsf{\Sigma_2 P}$, but not $\mathsf{\Sigma_2 P}$-complete unless $\mathsf{PH} = \mathsf{\Sigma_3 P}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.