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$ – Yuval Filmus Jul 21 '18 at 14:28

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.

| cite | improve this answer | |
  • $\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 '18 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 '18 at 3:40
  • $\begingroup$ @Mickey You are just making the problem more complicated. It's easier to reduce directly from SAT-C. $\endgroup$ – Yuval Filmus Jul 22 '18 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 '18 at 0:28

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

| cite | improve this answer | |

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.