<p>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.)</p>

<p>Let me also clarify: the problem you are asking about is more typically called Circuit <em>Equivalence</em>. Circuit <em>Isomorphism</em> 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}$. </p>

CC BY-SA 3.0
2014-01-26T03:51:12.237Z
2014-01-26T03:51:12.237Z
Joshua Grochow
<p>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.</p>

CC BY-SA 3.0
2014-01-24T22:06:19.467Z
Nope. Two non-isomorphic circuits can have the same function.
Chad Brewbaker
CC BY-SA 3.0
2014-01-24T22:14:27.277Z
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}$).
Marzio De Biasi
CC BY-SA 3.0
2014-01-24T22:36:15.393Z
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.
vzn
CC BY-SA 3.0
2014-01-25T00:23:40.530Z
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}$.
Joshua Grochow
CC BY-SA 3.0
2014-01-25T10:35:43.997Z
@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 ).
Marzio De Biasi
CC BY-SA 3.0
2014-01-25T21:39:57.400Z
Thanks a lot you guys for clarifying these things. All of my searches for "Circuit Equivalence" sent me to stuff in EE. It is hard to learn about problems when you don't know what they are called.
Eric Bahr
<cc.complexity-theory><graph-theory><graph-isomorphism>
How hard is the Circuit Isomorphism problem?
Eric Bahr
# How hard is the Circuit Isomorphism problem?

(Asked by: username_0 on 2014-01-24)

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.

**Tags:** cc.complexity-theory, graph-theory, graph-isomorphism

> **Comments:**
> **username_1**: Nope. Two non-isomorphic circuits can have the same function.  
> **username_2**: 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}$).  
> **username_3**: 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.  
> **username_4**: 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}$.  
> **username_2**: @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 ).  
> **username_0**: Thanks a lot you guys for clarifying these things. All of my searches for "Circuit Equivalence" sent me to stuff in EE. It is hard to learn about problems when you don't know what they are called.  

---

## 1 answers

### Answer by username_4 on 2014-01-26. Score: 12 | Accepted answer

As pointed out by @username_2, 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}$.


---

