# Cook’s Theorem | DAA

## Cook’s Theorem

SAT is NP-complete
Proof
To prove that SAT is NP—complete, we have to show that

• SATεNP
• SAT is NP-Hard

### SATεNP

Circuit satisﬁability problem (SAT) is the question “Given a Boolean combinational circuit, is it satisﬁable? i.e. does the circuit has assignment sequence of truth values that produces the output of the circuit as 1'?” Given the circuit satisﬁability problem take a circuit x and a certiﬁcate y with the set of values that produce output 1, we can verify that whether the given certiﬁcate satisﬁes the circuit in polynomial time. So we can say that circuit satisﬁability problem is NP.

### SAT is N P-hard

Take a problem V E NP, let A be the algorithm that veriﬁes V in polynomial time (this rnust be true since V E NP}. We can program A on a computer and therefore there exists a (huge) logical circuit whose input wires correspond to bits of the inputs x and y of A and which outputs l precisely when A(x,y} returns yes. For any instance x of V let Ax be the circuit obtained from A by setting the x-input wire values according to the speciﬁc string x. The construction ofAx from x is our reduction function.