Problem Detail: $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?
Asked By : user1675999
Answered By : Luke Mathieson
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7032
