6
$\begingroup$

$\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS.

$\cc = \{\langle C \rangle : C \text{ is a satisfiable combinatorial boolean circuit} \}$

Lemma: The $\cc$ problem is $\mathsf{NP}$-hard.

Can anyone provide an easy-to-understand proof?

$\endgroup$
  • $\begingroup$ CLRS is an algorithms textbook, if you want to understand it and its details I would suggest you check a complexity theory textbook like Sipser's. $\endgroup$ – Kaveh Nov 30 '12 at 7:02
7
$\begingroup$

The (very) simplified version is that they convert any verification algorithm $A$ for a language $L \in \text{NP}$ into a circuit.

What they end up with is a circuit $C$ that, given a (binary) string $x$ is satisfiable (i.e. $C(x)=1$) if and only if $x \in L$ (i.e. there exists a certificate $y$ such that $A(x,y) = 1$).

They do this by encoding the working of the algorithm embodied by some Turing Machine (i.e. the transition function) as a circuit $M$. The total circuit $C$ is then a series of concatenations of $M$, where the input values to each iteration of $M$ is a binary encoding of the state of the TM embodying $A$.

As every bit of this (including the number of steps $A$ takes) is polynomially bounded by the size of $x$, the circuit can be constructed in polynomial time.

So what they give overall is a polynomial time way to construct a circuit simulating $A$ set by step that is satisfiable if and only if we can find some certificate that $x \in L$. Then if we could decide in polynomial time if $C$ is satisfiable we'd know that there's some certificate which proves $x \in L$, hence deciding $L$ in polynomial time.

$\endgroup$
  • $\begingroup$ Just to clarify the turing machine, is the structure that contains M and A. I am just confused because the book states all of this stuff in a very compact format. Thanks $\endgroup$ – user1675999 Dec 1 '12 at 5:06
  • $\begingroup$ The Turing Machine isn't pictured, but is basically the algorithm $A$ (to say that something has an algorithm, in a theoretical sense, means there is a Turing Machine that computes the problem). The picture is a diagram of the circuit $C$, which contains $M$. These two bits coincide in that $M$ (given the appropriate state information - encoded as bits on the wires) does one step of $A$, taking it to the next state in the same way $A$ would if we ran the TM that executes $A$ on the same input. $\endgroup$ – Luke Mathieson Dec 1 '12 at 5:13
  • $\begingroup$ They assert that $M$ is polynomial in the input size. But i don't see it, because it may have any number of gates and wires. Can you, please, clarify it? $\endgroup$ – Yola Dec 26 '14 at 11:48

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.