# Simple proof that circuit satisfiability problem is NP-Hard

$\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?

• 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. – Kaveh Nov 30 '12 at 7:02

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.

• 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 – user1675999 Dec 1 '12 at 5:06
• 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. – Luke Mathieson Dec 1 '12 at 5:13
• 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? – Yola Dec 26 '14 at 11:48