15-451 Algorithms 11/10/04 * Linear programming * NP and NP-completeness ======================================================================= * Linear programming: - if you didn't do LP last time, you might want to go over the LP parts of the hwk that was due yesterday (fractional set-cover and/or multicommodity flow). Have a student present their answer. * NP and NP-completeness In order to get going with the whole theory of NP-completeness, we need to have some NP-complete problem to begin with. Here is a proof sketch from first principles that the following problem, called CIRCUIT-SAT, is NP-complete. CIRCUIT-SAT: Given a circuit of NAND gates with a single output and no loops (some of the inputs may be hardwired). Question: is there a setting of the inputs that causes the circuit to output 1? Proof Sketch: First of all, it is clearly in NP, since you can just guess the input and try it. Now, suppose some problem A is in NP. That means there is a polynomial-time verifier V that takes in an instance x and a solution/proof y, and then checks to see if y is really a solution/proof for x. (E.g., x is a graph and y is a tour). In other words, if x is a NO instance, then there should not exist any y such that V(x,y)=1. But, if x is a YES instance, then there should exist some y that causes V(x,y) to output 1. We are now going to use V to reduce problem A to CIRCUIT-SAT. Specifically, given some instance x, we want to create a circuit C_x such that C_x(y) = V(x,y). If we can do this, then C_x is a YES-instance of CIRCUIT-SAT (i.e., there exists y such that C_x(y)=1) iff x was a YES-instance of A (i.e., there exists y such that V(x,y)=1). How are we going to convert V and x into a circuit C_x? If we think of V as a computer program, we can do this by unrolling the loops of V, and having each layer of the circuit encode one time step of V's computation. The width of C_x will be the amount of memory used by V, and the depth of C_x will be the amount of time used by V. (Remember from 15-251 that a computer is just NAND gates with a clock, which means we can encode one step of computation by one layer of circuit.) Since V is polytime, this circuit will have polynomial size. We then hardwire the "x" part of the input wires to our given instance "x", producing the circuit C_x. We have now shown how to reduce any arbitrary problem A in NP to CIRCUIT-SAT. In other words, if we had an oracle for CIRCUIT-SAT, we could use it to solve any problem A in NP: given an input x we run the above procedure to produce C_x and then feed C_x into our oracle. I.e., we have shown that CIRCUIT-SAT is NP-complete. [If there is time, do reduction below] We can use this to prove that 3-SAT is NP-complete too. This reduction is important (and a little tricky) because 3-SAT looks so much simpler than Circuit-SAT. Nonetheless, we're going to prove that any algorithm to solve 3-SAT could be used to solve general circuit-SAT too. To prove this, we want to show how we can take a circuit-SAT instance (i.e., a circuit C where we want to know if there exists an input z that makes C(z)=1) and convert it into a 3-SAT instance that is satisfiable *iff* the circuit we were given is satisfiable. REDUCTION: We will create one variable for each *wire* in the circuit C. Say we have some gate g whose inputs are wires y_1 and y_2, and whose output wire is y_3. Since g is a NAND gate, we want to make sure that the output is NOT the AND of the two inputs. We can write this as: (y_1 OR y_2 OR y_3) // if y_1=0 and y_2=0 then we can't have y_3=0 AND (y_1 OR not(y_2) OR y_3) // if y_1=0 and y_2=1 then we can't have y_3=0 AND (not(y_1) OR y_2 OR y_3) // if y_1=1 and y_2=0 then we can't have y_3=0 AND (not(y_1) OR not(y_2) OR not(y_3)) // can't have all three = 1. We will do this for all gates in the circuit. Now, we will also have variables z_1,...,z_n for the input bits to C, and force any wire y_j connected to input z_i to have the same value as variable z_i: (y_j OR not(z_i)) AND (not(y_j) or z_i) Finally, we add one more clause saying that we want the output to be 1. This is easy: if y_m is the output wire, then we just add the clause (y_m). In other words, we are asking: is there an input and a setting of all the wires such that the output of the circuit is equal to 1, and each gate is doing what it's supposed to? So, the 3-CNF formula produced is satisfiable if and only if the circuit has a setting of inputs that causes it to output 1. The size of the formula is polynomial (actually, linear) in the size of the circuit. The construction can be done in polynomial (actually, linear) time. So, if we had a polynomial-time algorithm to solve 3-SAT, then we could solve circuit-SAT in poly time too.