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 satisfiability problem (SAT) is the question “Given a Boolean combinational circuit, is it satisfiable? i.e. does the circuit has assignment sequence of truth values that produces the output of the circuit as 1'?” Given the circuit satisfiability problem take a circuit x and a certificate y with the set of values that produce output 1, we can verify that whether the given certificate satisfies the circuit in polynomial time. So we can say that circuit satisfiability problem is NP.

SAT is N P-hard

Take a problem V E NP, let A be the algorithm that verifies 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 specific string x. The construction ofAx from x is our reduction function.