15-451 Algorithms 11/04/09 recitation notes * Recap of basic definitions of NP and NP-completeness * NP-completeness of integer programming * NP-completeness of 3-coloring ================================================================= * Recap of definitions and complexity classes. NP: decision problems where at least the YES-instances have short proofs (that can be checked in polynomial-time) that the answer is YES. Q is in NP if there is a verifier V(I,X) such that: If "I" is a YES-instance, then there exists X such that V(I,X) = YES. If "I" is a NO-instance, then for all X, V(I,X) = NO. and furthermore the length of X and the running time of V are poly in |I|. co-NP: Problems where the the NO-instances have short proofs. (E.g.,given two circuits, C_1, C_2, do they compute the same function?). Formally, Q is in co-NP if there is a verifier V(I,X) such that: If "I" is a YES-instance, then for all X, V(I,X) = YES. If "I" is a NO-instance, then there exists X such that V(I,X) = NO. and furthermore the length of X and the running time of V are poly in |I|. Problem Q is NP-complete if: (1) Q is in NP, and (2) Q' \leq_p Q for any other Q' in NP. If Q just satisfies (2) then it's called NP-hard. In class yesterday we proved that the 3-SAT problem is NP-complete. Remember, 3-SAT is: given a CNF formula over n variables with at most 3 literals per clause [give example], does there exist an asignment to the variables s.t. the formula is true. [make sure students understand what it means to satisfy a formula]. Today, lets use this fact to prove NP-completeness of other problems. To do this, we just need to show that (1) the new problem is in NP, and (2) that we can reduce 3SAT to the new problem. General idea of reduction: Reducing problem A to problem B =============================== To reduce problem A to problem B we want a function f that takes instances of A to instances of B such that: (1) if x is a yes-instance of A then f(x) is a yes-instance of B (2) if x is a no-instance of A then f(x) is a no-instance of B (3) f can be computed in polynomial time. So, if we had an algorithm for B, we could using it to solve A by running it on f(x). NP-COMPLETENESS OF INTEGER PROGRAMMING -------------------------------------- Integer linear programming (ILP) is like linear programming, with the additional constraint that all variables must take on integral values. The decision version of integer programming asks whether or not there exists a point satisfying all the constraints (for the decision version there is no objective function). Claim: ILP is NP-complete. Proof: (1) ILP is in NP. (2) We can reduce 3SAT to ILP: Let the variables in the 3SAT formula be x_1, x_2, ..., x_n. We will have corresponding variables z_1, z_2, ..., z_n in our integer linear program. First, restrict each variable to be 0 or 1: 0 <= z_i <= 1 for all i Assigning z_i=1 in the integer program represents setting x_i=true in the formula, and assigning z_i=0 represents setting x_i=false. For each clause like (x_1 OR not(x_2) OR x_3), have a constraint like: z_1 + (1-z_2) + z_3 > 0. To satisfy this inequality we must either set z_1=1 or z_2=0 or z_3=1, which means we either set x_1=true or x_2=false or x_3=true in the corresponding truth assignment. NP-COMPLETENESS OF 3-COLORING ============================= This reduction is a little trickier. Want to convert 3-CNF formula \phi to a graph G that is 3-colorable iff \phi was satisfiable. First, for each x_i, will have one node called "x_i" and one node called "not(x_i)". Let's call the three colors "red", "T" and "F", and add three special nodes in a triangle called "red", "T", and "F" that we can assume without loss of generality are given the corresponding colors. Now, let's have a triangle between red, x_i, and not(x_i) for each i. This forces the coloring to make a choice for each variable of whether it should be true or false. Now, we need to add in a "gadget" for each clause. For a clause "(x OR y or z)" we will have the gadget: x---O |\ | O---O |/ |\ y---O | T (this is the common "T" node) |/ z---------O This gadget has the property that it's not possible to color all three of x,y,z with color "F", but *any* other assignment of {T,F} to x,y,z is OK. [this is easiest to see looking at the triangle attached to x,y. If both x,y are F, then the tip of that triangle has to be F too, else it can be colored T.] So, if the formula was satisfiable then there is a legal 3-coloring, and any legal 3-coloring must give a satisfyting assignment to the formula.