6.046J Recitation 10: NP-Hardness

6.046 Recitation 10 April 27, 2012 Outline 1 Review 1.1 About NP . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 About NP-Hardness . . . . . . . . . . . . . . . . . . . 1 1 2 2 Proving NP-Hardness 2.1 Pick a Problem . . . 2.2 Relate the Witnesses 2.3 Add Constraints . . 2.4 Formalize . . . . . . 2 2 4 5 7 . . . . . . . . . . . . . . . . . . . . 3 Strong and Weak NP-Hardness 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Review In this recitation, we’ll be talking about how to prove that a problem is NP-hard. In order to do so, it’s a good idea to first review some definitions. The definitions of NP and NP-hardness can be very tricky to get at first, so it’s a good thing to make sure that we’re all on the same page. The first thing to take care of is actually even more basic: how do we define a problem? Is it very general or very specific? For instance, 3-Sat is a problem. But there’s a number of related problems, such as the problem of whether the boolean formula (x1 ∨ x2 ) ∧ (x2 ∨ x1 ) can be satisfied. For the purposes of this recitation, we’ll be calling 3-Sat a problem, and boolean formulae like the one above are called problem instances. 1.1 About NP With that out of the way, we can review the definition of NP. All problems in NP are decision problems, not search problems: the answer to a particular instance of the problem is always either True or False. However, for any decision problem there’s usually a related search problem. And if you’re trying to show that a search problem is NP-hard, it’s sufficient to show that the related decision problem is NP-hard. Informally, a problem is in NP if and only if it has a polynomialtime verifier. In other words, it is in NP if you can check whether the answer is correct in polynomial time. However, there’s a bit of a complication here. The answer to a decision problem is either True or False. So “checking” an answer seems like it would consist of taking as input the problem instance x and the answer True, and verifying that that was the correct answer. But it seems like if you could do that in polynomial-time, you ought to be able to solve x in polynomial-time. (Just try running the verifier with x and True as inputs.) 1 About NP. • Decision problems: solution to every prob­ lem instance is True or False. • Formally, there exists a poly-time algorithm A such that the answer to instance x is True iff there exists a poly-size witness y with A(x, y) = True. 6.046 Recitation 10 April 27, 2012 That’s where the idea of witnesses comes in. A witness y for a problem instance x is basically secret information that lets you verify that the answer to x is True. It’s usually the answer to the related search problem. For example, consider the question of whether the boolean formula (x1 ∨ x2 ) ∧ (x2 ∨ x1 ) can be satisfied. This is clearly an instance of the 3-Sat problem. The related search problem asks for a particular assignment that satisfies that formula. So the witness for the satisfiability of that problem would be an assignment such as x1 = True, x2 = True. There are a couple of things to note. First of all, the size of the witness y should be polynomial in the size of the problem instance x. Second, if a problem is in NP, then there are witnesses that attest to a particular problem instance being True, but there might not be any witnesses that attest to a particular problem instance being False. The decision problem is usually defined as, “Is there an answer to this related search problem?” So finding an answer to the related search problem is clearly a witness to the decision problem. But if there is no answer, there might not be an efficient way to check. 1.2 About NP-Hardness Now that we’ve reviewed the definition of NP, we can move on to the definition of NP-hardness. A problem is NP-hard if all problems in NP can be reduced to it in polynomial time. So if any NP-hard problem can be solved in polynomial time, then any problem in NP can also be solved in polynomial time. Unfortunately, this means that it seems rather difficult to show that anything is NP-hard. (Hav­ ing to show a reduction from every problem in NP from scratch every time seems like it would be very difficult.) Luckily, there’s a short­ cut: if you know that a problem A is NP-hard, then you can show that a problem B is NP-hard by giving a polynomial-time reduction from any instance of problem A to an instance of problem B. 2 • A problem is NP-hard if all problems in NP can be reduced to it. • To show NP-hardness, sufficient to reduce a known NP-hard problem to it. • A problem is NP-complete if it is NP-hard and in NP. Proving NP-Hardness This brings us to the main topic of this particular recitation: how to show that a problem is NP-hard. We’ll be approaching this from an algorithmic design perspective: not just giving an example of a proof of NP-hardness, but also showing how to come up with such a proof. The technique that we’ll be using boils down to the four steps listed to the right. We’ll be using those four steps in an attempt to prove that the Subset-Sum problem is NP-hard. 2.1 NP-Hardness and NP-Completeness. Pick a Problem The very first step in showing NP-hardness is to pick a problem to reduce from. Technically, there exists a polynomial-time reduction 2 Recipe for NP-Hardness. 1. 2. 3. 4. Pick a problem to reduce from. Relate the witnesses. Add constraints. Formalize. 6.046 Recitation 10 April 27, 2012 from every NP-complete problem to every NP-hard problem, so we could pick pretty much any problem. But some problems are a lot easier than others. It’s usually a good idea to pick a problem that is in some way related. To the right there is a list of the problems that are most commonly used to show NP-hardness. Some of these you may already know. However, for the sake of completeness, we’re going to repeat the definition of each. Definition 1. The 3-Sat problem is defined as follows: • Input: A boolean formula in conjunctive normal form such that there are at most three literals in each clause. • Output: True if and only if the formula is satisfiable. Definition 2. The Subset-Sum problem is defined as follows: • Input: A set S = {s1 , . . . , sn } of non-negative integers and a target value t. • Output: True if and only if there exists a subset of S that sums to t. Definition 3. The Vertex-Cover problem is defined as follows: • Input: A graph G = (V, E) and a non-negative integer k. • Output: True if and only if there exists a subset S of vertices such that |S| = k and all edges are incident to at least one vertex in S. Definition 4. The Clique problem is defined as follows: • Input: A graph G = (V, E) and a non-negative integer k. • Output: True if and only if there exists a subset S of ver­ tices such that |S| = k and the subgraph of G induced by S is complete. Definition 5. The Graph-Coloring problem is defined as follows: • Input: A graph G = (V, E) and a number of colors k ≥ 3. • Output: True if and only if there exists a way to assign each vertex a color such that no edge connects two vertices of the same color. These problems fall into three categories: booleans, numbers, and graphs. These categories can be useful in picking which problem to reduce from. If we’re trying to show that some problem related to booleans is NP-hard, then it might make sense to reduce from 3-Sat. If we’re trying to show that some problem related to numbers is NPhard, then it might make sense to reduce from Subset-Sum. If we’re 3 Known NP-Complete Problems. • • • • • 3-Sat Subset-Sum Vertex-Cover Clique Graph-Coloring 6.046 Recitation 10 April 27, 2012 trying to show that some problem related to graphs is NP-hard, then it might make sense to reduce from whichever of Vertex-Cover, Clique, or Graph-Coloring seems more closely related. In this recitation, we’re trying to show that Subset-Sum is NPhard. That’s a number-related problem, but unfortunately we can’t show that Subset-Sum is NP-hard by reducing from Subset-Sum. Instead, we’re going to do it by reduction from 3-Sat. Note that 3-Sat can often be a sort of catch-all — even when the problem doesn’t seem to be related to booleans, the reduction from 3-Sat can be quite straightforward in some cases. 2.2 Relate the Witnesses Now that we’ve picked a problem, it’s time to start constructing our reduction. Due to some complications with the definition of NP, we cannot use general Cook reductions to show that a problem is NP-hard. Instead, we must use Karp reductions. Recall that a Karp reduction from a problem A to a problem B is a function f mapping instances of problem A to instances of problem B such that for any instance x of A, the answer to x is True if and only if the answer to f (x) is True. If A and B are problems in NP, then we can use the definition of NP to rewrite the definition of a Karp reduction as follows. Let VA be the poly-time verifier for A, and let VB be the polytime verifier for B. Then f is a Karp reduction from A to B if and only if for all instances x of A, there is a poly-size witness y for the truth of x if and only if there is a poly-size witness z for the truth of f (x). More formally: There exists a poly-size witness y such that VA (x, y) = True. ⇐⇒ There exists a poly-size witness z such that VB (f (x), z) = True. What does this mean? Well, it means that if a witness exists for x, then there must be a witness for f (x), and vice versa. Logically, it seems like maybe these witnesses should be connected somehow. So that is our first step in building a reduction: find a mapping between the witnesses that seems like it might be useful. Let’s discuss what properties might be useful. The problem in­ stance x can be any instance of problem A, so we can’t place any constraints on the witness y. The problem instance f (x), on the other hand, is strictly determined by our reduction, and so we may be able to place constraints on the witness z. This mapping between witnesses should be two-way. We want to be able to construct the appropriate z given any y, and we want to be able to extract the value of y given the appropriate z. This is an encoding of sorts: we want all of the information in y to show up somewhere in z preferably in a way that’s pretty easy to extract. 4 Reduction Form. • For NP-hardness, must use Karp. • A Karp reduction from Problem A to Prob­ lem B is a function f mapping instances of A to instances of B such that: answer to x ⇔ answer to f (x) is True is True • If A and B are problems in NP with VA the verifier for A and VB the verifier for B, equivalent to: exists witness y : exists witness z : ⇔ VA (x, y) = True VB (f (x), z) = True 6.046 Recitation 10 April 27, 2012 It can be hard to understand what this process of relating wit­ nesses looks like without an example. So let’s return to our reduction from 3-Sat to Subset-Sum. A witness for 3-Sat assigns each vari­ able a value of True or False. A witness for Subset-Sum is a subset of numbers. So if we want to encode a variable assignment in a subset, it makes sense to create for each variable in our 3-Sat prob­ lem, a number in our Subset-Sum problem that will be included in the subset if and only if the variable is True. Does this idea work? Well, let’s do an example. Suppose that we start with the 3-Sat instance (x1 ∨ x2 ) ∧ (x2 ∨ x1 ). There are two variables x1 and x2 , so we would create two numbers in our SubsetSum instance: s1 and s2 . The assignment x1 = True, x2 = True is a witness for 3-Sat, so the corresponding Subset-Sum witness would be the set {s1 , s2 }. To make this work properly, we’d probably want to set t = s1 + s2 . But this doesn’t quite work properly. There’s another witness for the boolean formula above: x1 = False and x2 = False. This would correspond to the empty subset. So to make this work properly, we’d probably want to set t = 0. Combined with the constraints on nonnegativity, this means that s1 = s2 = 0. This seems wrong. How can we fix this? Well, the problem seems to be that when we set a variable to false, nothing shows up in the corresponding subset. So intuitively, it seems like the target value we’re looking for should be roughly proportional to the number of variables that need to be true to create a satisfying assignment. (If we assume that all of the numbers are roughly the same size.) But we don’t know how many variables need to be true to create a satisfying assignment. So let’s take a different approach. Let’s make each variable xi have two numbers siT and siF in the corresponding Subset-Sum instance. The number siT should be included in the subset if and only if xi is set to True. The number siF should be included in the subset if and only if xi is set to False. We’ll have to figure out how to enforce those constraints later, but in the meantime this seems to fix our problem. Now the witness x1 = True, x2 = False corresponds to the subset {s1T , s2T }, while the witness x1 = False, x2 = False corresponds to the subset {s1F , s2F }. And it’s not out of the realm of possibility to have s1T + s2T = t = s1F + s2F . 2.3 Witnesses Example. • 3-Sat Witness: Satisfying assignment of True or False to all variables. • Subset-Sum Witness: Subset of numbers that sums to the target. First Idea. • For each variable in the 3-Sat instance, make a corresponding number in the Subset-Sum instance. • Variable is True iff corresponding number is included in Subset-Sum witness. Second Idea. • For each variable xi in the 3-Sat instance, make two corresponding numbers siT and siF in the Subset-Sum instance. • xi = True ⇔ siT included in subset • xi = False ⇔ siF included in subset Add Constraints We have made a decision about how we want the witnesses y and z to relate to each other. Now it’s time to make sure that y is a witness for x only when z is a witness for f (x), and vice versa. This step usually requires rephrasing the constraints of Problem A (the problem we’re reducing from) in terms of the constraints of Problem B (the problem we’re reducing to). Essentially, there are certain constraints that determine whether or not a given string y is a witness for the problem instance x. We have to somehow simulate 5 Add Constraints. • Figure out constraints imposed on witness y by Problem A. • Figure out constraints imposed on witness z by Problem B. • Want to simulate constraints of Problem A using constraints from Problem B. 6.046 Recitation 10 April 27, 2012 those constraints using the constraints that determine whether or not a given string z is a witness for the problem instance f (x). Unfortunately, this step is by far the most difficult to understand in its full generality. So let’s see how it applies to the problem that we’ve been working on. Let’s try to understand the types of constraints in 3-Sat and in Subset-Sum. Any witness for 3-Sat has the following properties: 1. Variables are assigned to be either True or False. No variable can be given more than one value. All variables must be given a value. 2. In each clause of the boolean formula, at least one of the literals must be true. The constraints for Subset-Sum are: Understanding Constraints. • Constraints on 3-Sat witnesses: 1. all variables True or False 2. cannot be both 3. all clauses contain a true literal • Constraints on Subset-Sum witnesses: 1. must be a subset 2. must sum to t 1. The numbers in the witness must all come from S, the set of numbers in the Subset-Sum instance. No number can be used more than once. 2. All of the numbers in the witness must sum to t. At first, this seems like a rather tough task. The constraints on 3­ Sat are myriad: one independent constraint for each clause. The constraints on Subset-Sum are comparatively simple: the witness must be a subset, and it must sum to the correct value. Let’s start by figuring out how to simulate the first 3-Sat con­ straint: that all variables must be assigned to either True or False, but not both. We have decided that for a variable xi , the number siT should be included in the Subset-Sum witness if and only if xi = True in the corresponding 3-Sat witness. Similarly, the num­ ber siF should be included in the Subset-Sum witness if and only if xi = False in the corresponding 3-Sat witness. So the equivalent of making sure that xi is assigned to either True or False but not both would be to make sure that either siT or siF shows up in the witness z, but not both. To tackle this problem, let’s look at a smaller case. Suppose we only have one variable x1 . Then there are two numbers in the Subset-Sum problem: s1T and s1F . We want to make sure that exactly one of them is selected for the subset. If we don’t have to satisfy any other constraints, then it’s sufficient to set s1T = s1F = t. That way, we pick exactly one for the subset. We may generalize this as depicted at right: each variable xi has a unique power of 2 associated with it. If s1T and s1F are both included in some subset, then the sum of the subset must be even. But t is odd, so exactly one of s1T and s1F must be included in the subset. By induction, we can show that for each variable xi , exactly one of siT and siF must be included to make the sum work out properly. 6 Variables Not Both True and False. • Simple Example: Only one variable, x1 . – Want the subset summing to t to con­ tain exactly one of s1T and s1F . – Idea: Make s1T , s1F = t. • General Case: Extend to more variables. – Idea: For each variable xi , set siT = siF = 2i−1 . Then set t = 2n − 1. – Written out in binary: s1T = s1F = s2T = s2F = s3T = s3F = s4T = s4F = t= 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 – Realization: Can use different bits in numbers to impose different con­ straints. 6.046 Recitation 10 April 27, 2012 This construction won’t completely work, in practice. (All num­ bers in the Subset-Sum problem must be unique.) But it gives us some intuition on how to construct constraints: if we can avoid or limit carries, then different bits of the number can be used to impose different constraints. We can use this idea in an attempt to impose all of the 3-Sat constraints. The other kind of 3-Sat constraints we need to simulate are the clause constraints. For each clause, there are three assignments of the form xi = True or xi = False that could cause the clause to be satisfied. At least one of those assignments must be included in the set of assignments used to satisfy the whole formula. We can rephrase this in terms of the Subset-Sum instance: for each clause, there are three numbers that, when included in the subset, correspond to satisfying the clause. We want to add constraints to our Subset-Sum instance to ensure that at least one of these three numbers is included in the subset. At right, we depict one way to do this. Each clause gets several bits associated with it, and the numbers associated with satisfying that clause have a value of 1 in the bits associated with that clause. But what should the target value be? Well, the number of assign­ ments that satisfy the clause should be at least one, but it could be as high as three. So we need some way to make sure that no mat­ ter how many true literals the clause contains for a given satisfying assignment, the sum works out properly. To do so, we add extra values to fill the gap for each clause. If the extra values sum to at most 3 within the bits devoted to that clause, then by setting the target value to 4 within those bits, we can ensure that each clause must contain at least one true literal. 2.4 Formalize Now that we’ve figured out most of the details, it’s time to for­ malize the reduction. Suppose that we’re given an instance of 3-Sat with n variables x1 , . . . , xn and m clauses c1 , . . . , cm . Then we con­ struct the numbers in our Subset-Sum instance as follows: • For each variable xi , let CiT = {j | xi ∈ cj } be the indices of the clauses that contain the literal xi . Then define the number siT as follows: siT = 1 · 23(i+m−1) + 1 · 23(j−1) j∈CiT • For each variable xi , let CiF = {j | xi ∈ cj } be the indices of the clauses that contain the literal xi . Then define the number siF as follows: siF = 1 · 23(i+m−1) + 1 · 23(j−1) j∈CiF 7 Clause Constraints. • Assign each clause several bits. • For each variable assignment xi = True or xi = False, modify the variable siT or siF to have a 1 in all of the clauses that the assignment would satisfy. • Example: (x1 ∨ x2 ) ∧ (x2 ∨ x1 ) ∧ (x1 ∨ x2 ) – Clause c1 = (x1 ∨ x2 ). – Clause c2 = (x2 ∨ x1 ). – Clause c3 = (x1 ∨ x2 ). s1T = s1F = s2T = s2F = t= x2 000 000 001 001 001 x1 001 001 000 000 001 c3 001 000 001 000 ??? c2 000 001 001 000 ??? c1 001 000 000 001 ??? 6.046 Recitation 10 April 27, 2012 • For each clause cj , define two numbers: rj1 = 1 · 23(j−1) rj2 = 2 · 23(j−1) We then define the target sum t to be: t= n X 1 · 23(i+m−1) + i=1 m X 4 · 23(j−1) j=1 All that remains now is to prove that this construction is correct. We may do so by arguing about the witnesses: that a witness for the original 3-Sat instance can be transformed into a witness for the corresponding Subset-Sum instance, and vice versa. 3 Strong and Weak NP-Hardness One thing to note about the above reduction is the magnitude of the numbers that we use. Note that the magnitude of the numbers is exponential in m and n. If those numbers are written in binary, this is not a problem: it takes O(m + n) time to write down a number with O(m + n) bits. So this reduction requires polynomial time if the numbers are written in binary. Suppose that we wanted to write those numbers in unary. Writing a number in unary means writing down a sequence of symbols whose length is equal to the magnitude of the number. This would require O(2O(m+n) ) time. So the reduction would stop being polynomialtime if the numbers were written in unary. Consider a variant of the Subset-Sum problem where all input numbers are written in unary. Call this new problem Subset-SumUnary. This problem can actually be solved in time polynomial in the size of the input, using a simple dynamic programming algorithm. As a result, the Subset-Sum problem is what’s known as weakly NPhard — if the numbers are written in unary, it’s not NP-hard at all. By contrast, a problem is strongly NP-hard if the problem is hard even when the numbers are written in unary. 8