Circuit satisfiability problem : SAT-C to SAT-2C

Question

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!

Answer 1

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

Answer 2

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.