Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
3  
To make this question a bit more enduring and useful to others, would you be able to expand the question to actually state what the Lemma is rather than just giving the number, and give the full reference for Cormen et al.? –  Luke Mathieson Nov 30 '12 at 3:54
    
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
    
I added the whole lemma from the pdf. –  user1675999 Dec 1 '12 at 5:08
    
@user1675999, I don't think Luke wanted you to add the proof of the lemma, but the statement of the lemma itself. –  Nicholas Mancuso Dec 1 '12 at 5:11
add comment

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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