I have the following language : $L=\{\langle C_1,C_2\rangle \text{ | } C_1 \text{ and } C_2 \text{ are two circuits that calculate different function}\}$. We can call this language SAT-2C.

Prove that $L$ is NP-complete.

1) Proving that $L \in$ NP is pretty simple : given the values of $C_1$, $C_2$, it is possible to verify if the result is true or false. The time required to do so is probably linear to the size of the circuits.

I'm stuck at step (2) of my proof :(

2) Since we know that SAT-C is a NP-Complete, we can try the following reduction : SAT-C $\le_p$ SAT-2C.

So if we have a circuit $\langle c \rangle \in \text{SAT-C}$, there must be a function $f$ that turns it into two circuits (if we want to prove that the reduction is possible)

$f(c) \rightarrow (c_1,c_2)$.

For example, if our circuit is $(a \land b)$ (logical AND).

The first circuit could be the same as c --- $c_1 = c = (a \land b)$.

But what about the second circuit? How can $c_2$ calculate a different function than $c_1$ BUT at the same time, allow a reduction from the other way (SAT-2C to SAT-C)?

Any helps or suggestions would be greatly appreciated!

  • 1
    $\begingroup$ Try a circuit which computes a constant function. $\endgroup$ Jul 21, 2018 at 14:28

2 Answers 2


As suggested by Yuval Filmus in the comment, you can try a circuit that always evaluates to False.


You can use a reduction from $\text{3-SAT}$.

$\text{3-SAT}$ is the language of $\text{CNF}$ formulas where each clause has at most three literals, and they are satisfiable, meaning - given a formula $\phi$ in the correct form, it is in $\text{3-SAT}$ iff there exists $x$ for which $\phi(x)=1$.

Now, you want to show that the language of two circuits that calculate two different functions is $\text{NPC}$, therefore, given a formula $\phi$ which is satisfiable, you want to create a reduction that transform this formula into two circuits, that calculate different functions.

First, transforming a $\text{3CNF}$ formula into a circuit can be done in polynomial time. So - you can construct one circuit. You now need to think of the other circuit. As Yuval Filmus mentioned, think of a circuit of constant size. What circuit will guarantee that if $\phi$ is satsfiable, than that circuit will calculate a different function than $\phi$, but if $\phi$ is not satisfiable, it will calculate the same function exactly?

Most of the answer is given, you are only left to think of that circuit. If you want, ask in the comments and I'll edit it in.

  • $\begingroup$ Hm, so I have to use 3-SAT instead of SAT-C? I'll give that a try! Do you have a link to the meaning of a constant size circuit? (Could be because i'm unable to translate it in French or to a term my teacher used in class!) $\endgroup$
    – Robert
    Jul 22, 2018 at 2:11
  • $\begingroup$ @Robert Since $\text{SAT-C}$ is also $\text{NPC}$ you can also do a reduction from it, I just gave a reduction from $\text{3-SAT}$ which I believe is really intuitive. A constant size circuit is just like its name - a circuit of a constant size, meaning it is not dependent on the size of the input. $\endgroup$
    – Mickey
    Jul 22, 2018 at 3:40
  • $\begingroup$ @Mickey You are just making the problem more complicated. It's easier to reduce directly from SAT-C. $\endgroup$ Jul 22, 2018 at 6:55
  • $\begingroup$ @Mickey : Would this work? c1=ϕ c2 = ϕ ^ x So if ϕ is true, then c2 will calculate a different function. However, if it's false, then the function ends with the same result $\endgroup$
    – Robert
    Jul 28, 2018 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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