1 00:00:00,012 --> 00:00:02,644 This video is a segway between bad news and good news. 2 00:00:02,644 --> 00:00:05,594 The bad news, which we have now discussed, is NP completeness. 3 00:00:05,594 --> 00:00:09,392 The fact that there are computationally intractable problems out there in the 4 00:00:09,392 --> 00:00:11,709 world. In fact, they are fairly ubiquitous and 5 00:00:11,709 --> 00:00:14,462 you're likely to encounter them in your own projects. 6 00:00:14,462 --> 00:00:18,237 The good new is that NP completeness is hardly a death sentence. 7 00:00:18,237 --> 00:00:23,162 Indeed, our algorithmic tool box is now rich enough to provide many different 8 00:00:23,162 --> 00:00:26,534 strategies toward coping with NP complete problems. 9 00:00:26,534 --> 00:00:30,058 So suppose you have identified a computational problem on which the 10 00:00:30,058 --> 00:00:32,310 success of your new startup company rests. 11 00:00:32,310 --> 00:00:36,358 May be you would spend the last several weeks throwing the kitchen sink at in. 12 00:00:36,358 --> 00:00:40,584 All the algorithm design paradigms you know, all the data structures, all the 13 00:00:40,584 --> 00:00:45,622 primitives, nothing works. Finally, you decide to try to prove the problem is NP 14 00:00:45,622 --> 00:00:48,974 complete, and you succeed. Now you have an explanation for why your 15 00:00:48,974 --> 00:00:53,771 weeks of effort have come to naught, but that doesn't change the fact that this is 16 00:00:53,771 --> 00:00:56,949 the problem that governs the success of your project. 17 00:00:56,949 --> 00:01:01,727 What should you do? Well, the good news is, NP completeness is certainly not a 18 00:01:01,727 --> 00:01:04,927 death sentence. There are people solving, or at least 19 00:01:04,927 --> 00:01:08,517 approximately solving, NP complete problems all the time. 20 00:01:08,517 --> 00:01:13,452 However, knowing that your problem is NP complete does tell you where to set your 21 00:01:13,452 --> 00:01:16,522 expectations. You should not expect some general 22 00:01:16,522 --> 00:01:20,995 purpose, super-fast algorithm, like we have for other computational problems, 23 00:01:20,995 --> 00:01:23,954 like say, sorting, or single source shortest paths. 24 00:01:23,954 --> 00:01:28,391 Unless you are dealing with unusually small, or well structured inputs, you're 25 00:01:28,391 --> 00:01:32,659 going to have to work pretty hard to solve this problem, and also, possibly, 26 00:01:32,659 --> 00:01:36,852 make some compromises. The rest of this course is devoted to 27 00:01:36,852 --> 00:01:41,070 strategies for solving or approximately solving NP- complete problems. 28 00:01:41,070 --> 00:01:45,694 In the rest of the video, I'll give you an orientation for what those strategies 29 00:01:45,694 --> 00:01:50,802 are, and what you can expect to come. So as usual, I'm going to to focus here 30 00:01:50,802 --> 00:01:56,188 on general purpose strategies that cut across multiple application domains. 31 00:01:56,188 --> 00:02:00,332 As usual, these general principles should just be a starting point. 32 00:02:00,332 --> 00:02:05,062 You should take them, and run with them, augmenting them with whatever domain 33 00:02:05,062 --> 00:02:09,164 expertise you have, in the specific problem that you need to solve. 34 00:02:09,164 --> 00:02:13,844 The first strategy, is to focus on computationally tractable special cases, 35 00:02:13,844 --> 00:02:17,720 of an np complete problem. Related, relatedly you want to think 36 00:02:17,720 --> 00:02:23,261 about what's special about your domain or about the data sets that you're working 37 00:02:23,261 --> 00:02:27,480 with, and try to understand if there's special structure which can be exploited 38 00:02:27,480 --> 00:02:30,671 in your algorithm. Let me point out, we've already done this 39 00:02:30,671 --> 00:02:34,649 in a couple of cases in this course. The first example we saw concerns the 40 00:02:34,649 --> 00:02:38,396 weighted independent set. So we started this problem on path graphs 41 00:02:38,396 --> 00:02:42,118 but computational problem makes perfect sense in general graphs. 42 00:02:42,118 --> 00:02:46,486 The general problem is I give you as input, an undirected graph, every vertex 43 00:02:46,486 --> 00:02:50,457 has a weight, and I want the maximum weight subset of vertices that is an 44 00:02:50,457 --> 00:02:54,403 independent set. And remember, in an independent set, you 45 00:02:54,403 --> 00:02:57,310 are forbidden to take any 2 vertices that are neighbors. 46 00:02:57,310 --> 00:03:01,294 So in an independent set, none of the pairs of vertices that you've picked are 47 00:03:01,294 --> 00:03:04,052 joined by an edge. In general graphs, the way to do an 48 00:03:04,052 --> 00:03:08,235 independent set problem is NP complete, so we certainly don't expect it to have a 49 00:03:08,235 --> 00:03:11,752 polynomial time algorithm. But, in the special case where the graph 50 00:03:11,752 --> 00:03:15,954 is a path, as we saw, there's a linear time, dynamic programming algorithm, that 51 00:03:15,954 --> 00:03:18,257 exactly solves the weight of the independent set problem. 52 00:03:19,411 --> 00:03:23,092 So path graphs form a special case of the weight of the weighted independent set 53 00:03:23,092 --> 00:03:27,521 problem that's computationally tractable, solvable in polynomial, even linear, 54 00:03:27,521 --> 00:03:30,051 time. In fact, the frontier of tractability can 55 00:03:30,051 --> 00:03:33,814 be pushed well beyond path graphs. On the homework, I asked you to think 56 00:03:33,814 --> 00:03:37,805 through the case of graphs that are trees, and notice that you could still do 57 00:03:37,805 --> 00:03:41,764 dynamic programming efficiently, to be weighted independent sets and trees. 58 00:03:41,764 --> 00:03:45,441 You can even get computationally efficient algorithms for a broader class 59 00:03:45,441 --> 00:03:47,718 of graphs, known as bounded tree width graphs. 60 00:03:47,718 --> 00:03:51,599 So the definition of that is a little outside the scope of this course, but you 61 00:03:51,599 --> 00:03:55,050 can go even beyond trees. So the second example follows from my 62 00:03:55,050 --> 00:03:59,470 dynamic programming algorithm for the Knapsack problem, so we discussed that 63 00:03:59,470 --> 00:04:02,618 running time and we explain why it's exponential time. 64 00:04:02,618 --> 00:04:06,748 The running time of our dynamic programming Knapsack algorithm is N, the 65 00:04:06,748 --> 00:04:09,946 number of items times capital W, the Knapsack capacity. 66 00:04:09,946 --> 00:04:14,552 And because it only takes log W bits to specify the capacity capital W, we don't 67 00:04:14,552 --> 00:04:19,143 call that a polynomial time algorithm. But, imagine you only have to solve a 68 00:04:19,143 --> 00:04:24,142 knapsack instance where the capacity is not too big, maybe even say that capacity 69 00:04:24,142 --> 00:04:28,751 capital W is Big O event, and you definitely will see knapsack instances in 70 00:04:28,751 --> 00:04:33,407 practice, which possess that property. Well then our dynamic programming 71 00:04:33,407 --> 00:04:37,852 algorithm just runs in time, O(n^2), and that's a bonafide polynomial time 72 00:04:37,852 --> 00:04:41,597 algorithm for this special case of a small knapsack capacity. 73 00:04:41,597 --> 00:04:45,482 So next, let me mention a couple of examples we're going to see in the 74 00:04:45,482 --> 00:04:48,722 forthcoming videos. The first one is going to concern the 75 00:04:48,722 --> 00:04:52,066 2-SAT Problem. The 2-SAT is a type of constraint 76 00:04:52,066 --> 00:04:55,036 satisfaction problem. You remember, in a constraint 77 00:04:55,036 --> 00:04:59,376 satisfaction problem, you have a bunch of variables, each one gets assigned a 78 00:04:59,376 --> 00:05:03,558 value. So the simplest case is the Boolean case, where each variable can be 79 00:05:03,558 --> 00:05:07,840 0 or 1, false or true, and then you have a bunch of clauses, which specify the 80 00:05:07,840 --> 00:05:11,263 permitted joint values of a collection of variables. 81 00:05:11,263 --> 00:05:16,217 The 2 in 2-SAT refers to the fact that each constraint involves the joint values 82 00:05:16,217 --> 00:05:20,247 of only a pair of variables. So, a canonical constraint in a two set 83 00:05:20,247 --> 00:05:25,176 instance, is going to for two variables, specify three joint assignments that are 84 00:05:25,176 --> 00:05:29,449 allowed and one that's forbidden. So for example may be it will say offer 85 00:05:29,449 --> 00:05:33,584 variables x3 and x7, it's okay to set them both to true, its okay to set them 86 00:05:33,584 --> 00:05:38,354 both to false, its okay to set 3 to true and 7 to false, but it's forbidden to set 87 00:05:38,354 --> 00:05:42,450 3 to false and 7 to true. So that's a canonical constraint in a 88 00:05:42,450 --> 00:05:46,704 2-SAT instance. 3-SAT, it's the same thing, except the constraints involve the 89 00:05:46,704 --> 00:05:50,653 joint values to a triple of variables, and it's going to forbidden one out of 90 00:05:50,653 --> 00:05:54,997 the eight possibilities. Now the 3 set problems are a conanicle NP 91 00:05:54,997 --> 00:05:59,007 complete problem. That was really singled out by Cook and 92 00:05:59,007 --> 00:06:03,947 Levin as being sufficiently expressive to encode all problems in NP. 93 00:06:03,947 --> 00:06:08,797 But, if each constraints had size only two, then, as we'll see, the problem 94 00:06:08,797 --> 00:06:12,852 becomes polynomial times solvable. There's a couple of ways of proving that. 95 00:06:12,852 --> 00:06:16,711 We're going to talk about a local search algorithm that checks whether or not 96 00:06:16,711 --> 00:06:20,830 there is indeed an assignment to the, variables that simultaneously satisfies 97 00:06:20,830 --> 00:06:24,852 all of the given constraints. So the final example, we'll discuss in 98 00:06:24,852 --> 00:06:29,517 more detail later, but just very briefly, we're going to discuss the vertex cover 99 00:06:29,517 --> 00:06:31,537 problem. This is a graph problem, 100 00:06:31,537 --> 00:06:35,177 and the vertex cover is just a complement of an independent set. 101 00:06:35,177 --> 00:06:39,802 So while an independent set cannot take two vertices from the same edge, in the 102 00:06:39,802 --> 00:06:44,652 vertex cover problem, you have to take at least one vertex from, every single edge. 103 00:06:44,652 --> 00:06:48,896 And then what you want is you want the vertex cover that minimizes the sum of 104 00:06:48,896 --> 00:06:52,383 the vertex weights. Yet again, this is an NP complete problem 105 00:06:52,383 --> 00:06:56,391 in general, but we're going to focus on the special case where the optimal 106 00:06:56,391 --> 00:06:59,630 solution is small. That is, we're going to focus on graphs, 107 00:06:59,630 --> 00:07:04,692 where there's a small number of vertices, such that every single edge has at least 108 00:07:04,692 --> 00:07:09,686 one N point in that small set, and we see that for that special case, using a smart 109 00:07:09,686 --> 00:07:14,058 kind of exhaustive search we'll actually be able to solve the problem in 110 00:07:14,058 --> 00:07:17,386 polynomial time. So let me reiterate that these tractable 111 00:07:17,386 --> 00:07:21,828 special cases are meant primarily to be building blocks, upon which you can draw 112 00:07:21,828 --> 00:07:25,761 in a possibly more sophisticated approach to your NP complete problem. 113 00:07:25,761 --> 00:07:29,347 So just to make this a little more concrete, let me just kind of dream up 114 00:07:29,347 --> 00:07:32,375 one scenario to let you know what I am thinking about. 115 00:07:32,375 --> 00:07:36,395 Imagine, for example, that you have a project where unfortunately it's not 116 00:07:36,395 --> 00:07:40,577 really 2-SAT that you're confronting, it's actually a 3-SAT instance. So you're 117 00:07:40,577 --> 00:07:44,492 feeling kind of bummed, 3-SAT is NP complete, and maybe you have 1000 118 00:07:44,492 --> 00:07:48,527 variables, and certainly you can't do brute force search over the 2 to the 119 00:07:48,527 --> 00:07:52,282 1,000 possible ways of assigning values to your 1000 variables. 120 00:07:52,282 --> 00:07:56,462 But, maybe the good news is, because you have domain expertise, because you 121 00:07:56,462 --> 00:07:59,752 understand this problem instance, you know that, yeah, 122 00:07:59,752 --> 00:08:03,493 there's 1,000 variables, but there's really 20 that are crucial. 123 00:08:03,493 --> 00:08:07,786 You have a feeling, that all of the action, basically, is boiling down to how 124 00:08:07,786 --> 00:08:12,212 these 20 core variables get assigned. Well now, maybe you can mix together some 125 00:08:12,212 --> 00:08:15,892 brute force search with some of these tractable special cases. 126 00:08:15,892 --> 00:08:20,185 For example, you can ennumerate over all 2 to the 20 ways of assigning values to 127 00:08:20,185 --> 00:08:25,101 this core set of 20 variables. 2 to the 20 is roughly a million, that's 128 00:08:25,101 --> 00:08:27,947 not so bad. And now, what you're going to do is, for 129 00:08:27,947 --> 00:08:32,354 each of these million scenarios, you check whether there's a way to extend 130 00:08:32,354 --> 00:08:36,939 that tentative assignment of 20 values to the 20 variables, to the other 980 131 00:08:36,939 --> 00:08:40,286 variables, so that all of the constraints get satisfied. 132 00:08:40,286 --> 00:08:45,191 The original problem is solvable if and only if there exists a way of assigning 133 00:08:45,191 --> 00:08:49,586 values to these 20 variables that successfully extends to the other 980. 134 00:08:49,586 --> 00:08:53,790 Now, because these are the crucial variables and it's where all the action 135 00:08:53,790 --> 00:08:57,998 is, maybe as soon as you assign all of them, 0's and 1's the residual SAT 136 00:08:57,998 --> 00:09:01,322 instance is tractable. For example, maybe it just becomes a 137 00:09:01,322 --> 00:09:04,807 simple 2-SAT instance, and then you can solve it in polynomial time. 138 00:09:04,807 --> 00:09:07,223 So this gives you a hybrid appoach, approach. 139 00:09:07,223 --> 00:09:11,303 Brute force search at the top level, tractable special cases for each guess of 140 00:09:11,303 --> 00:09:14,482 assignment of the 20 variables, and you're off to the races. 141 00:09:14,482 --> 00:09:18,180 And I hope it's clear, I mean this as just one possible way that you might 142 00:09:18,180 --> 00:09:22,674 combine the various building blocks we're developing into a more elaborate approach 143 00:09:22,674 --> 00:09:26,552 to tackling NP complete problem. And that's generally what they take, they 144 00:09:26,552 --> 00:09:30,536 take a fairly elaborate approach, because, after all, they are NP complete, 145 00:09:30,536 --> 00:09:34,747 you've gotta respect that. So with that digression complete, let me 146 00:09:34,747 --> 00:09:39,084 mention what are the other two strategies we're going to be exploring in the 147 00:09:39,084 --> 00:09:42,308 lectures to come. So the second strategy, which is 148 00:09:42,308 --> 00:09:46,441 certainly one very common in practice, is to resort to heuristics. 149 00:09:46,441 --> 00:09:50,743 That is, two algorithms, which are not guaranteed to be correct. 150 00:09:50,743 --> 00:09:54,905 We haven't really seen examples of heuristics in the course thus far. those 151 00:09:54,905 --> 00:09:59,156 of you that are alumni of part 1, perhaps we could classify Carger's randomized 152 00:09:59,156 --> 00:10:02,755 minimum cut algorithm as a heuristic, because it did have a small failure 153 00:10:02,755 --> 00:10:05,563 probability of failing to find, the minimum cut. 154 00:10:05,563 --> 00:10:09,276 But rather, I'm going to focus on some examples in the upcoming lectures. 155 00:10:09,276 --> 00:10:12,283 I'm going to use the. Knapsack problem as a case study, 156 00:10:12,283 --> 00:10:16,330 and what we'll see, is that our toolbox, which contains various algorithm design 157 00:10:16,330 --> 00:10:20,136 paradigms, it's useful not just for designing correct algorithms, but it's 158 00:10:20,136 --> 00:10:24,129 also useful for designing heuristics. So in particular, we'll get a pretty good 159 00:10:24,129 --> 00:10:28,180 algorithm for the Knapsack problem, using the greedy algorithm design paradigm, 160 00:10:28,180 --> 00:10:32,736 and we'll get an excellent Heuristic for Knapsack, using the dynamic programming 161 00:10:32,736 --> 00:10:36,091 algorithm design pardigm. The final strategy, is for situations 162 00:10:36,091 --> 00:10:38,475 where you are unwilling to relax correctness. 163 00:10:38,475 --> 00:10:42,434 You're unwilling to consider heuristics. Now, of course, for an NP complete 164 00:10:42,434 --> 00:10:46,362 problem, if you're always going to be correct, you're not, you don't expect to 165 00:10:46,362 --> 00:10:50,408 run in polynomial time, but there are still opportunities to have algorithms 166 00:10:50,408 --> 00:10:54,914 that, while exponential time in the worst case, are smarter than naive brute force 167 00:10:54,914 --> 00:10:57,045 search. So we have in fact already seen one 168 00:10:57,045 --> 00:11:01,239 example that can be interpreted as a implementation of this strategy, that's 169 00:11:01,239 --> 00:11:04,781 for the knapsack problem. So, in the knapsack problem, naive brute 170 00:11:04,781 --> 00:11:08,380 force search, would just run over all possible subsets of the items. 171 00:11:08,380 --> 00:11:11,213 It would check if a subset of items fit in the knapsack. 172 00:11:11,213 --> 00:11:15,254 If it does, it remembers the value, and then it just returns the feasible 173 00:11:15,254 --> 00:11:16,690 solution. with maximum value. 174 00:11:16,690 --> 00:11:21,046 That has time proportional to 2 to the n, where n is the number of items. 175 00:11:21,046 --> 00:11:24,384 Our dynamic programming algorithm, has running time n times W. 176 00:11:24,384 --> 00:11:28,604 Now, of course, cap- this is no better than 2 to the n, if the knapsack capacity 177 00:11:28,604 --> 00:11:32,676 is huge, if it is itself, 2 to the n. But, as we argued, if W is smaller, this 178 00:11:32,676 --> 00:11:36,461 algorithm is going to be faster. And also, as you learned on the third 179 00:11:36,461 --> 00:11:40,977 programming assignment, sometimes even though W is big, dynamic programming's 180 00:11:40,977 --> 00:11:43,692 going to beat the crap out of brute force search. 181 00:11:43,692 --> 00:11:46,030 So I'll show you a couple of other examples. 182 00:11:46,030 --> 00:11:50,274 We'll talk about the travelling salesman problem, where naive brute force search 183 00:11:50,274 --> 00:11:54,129 would roughtly take n factorial time, where n is the number of vertices. 184 00:11:54,129 --> 00:11:58,058 We'll give an alternative dynamic programming base solution which runs in 185 00:11:58,058 --> 00:12:00,952 time only 2 to the n, which is much better than n factorial. 186 00:12:00,952 --> 00:12:05,328 The third example which will cover in a forthcoming video, we already alluded to 187 00:12:05,328 --> 00:12:08,556 briefly on the last slide. It's for the vertex cover problem. 188 00:12:08,556 --> 00:12:12,763 So this is where you're given a graph, every vertex has a weight, you want the 189 00:12:12,763 --> 00:12:17,865 minimum weight subset of vertices that includes at least one endpoint from every 190 00:12:17,865 --> 00:12:20,375 edge. We're going to consider the version of 191 00:12:20,375 --> 00:12:24,892 the problem where you want to check whether or not it's possible to have a 192 00:12:24,892 --> 00:12:29,739 vertex cover that uses only k vertices, whether or not there exists k vertices 193 00:12:29,739 --> 00:12:32,786 that includes one endpoint at least, from each edge. 194 00:12:32,786 --> 00:12:37,708 The naive brute force search will run in time, end the k, which gets absurd, even 195 00:12:37,708 --> 00:12:40,842 when k is quite small, but we're going to show that there's a 196 00:12:40,842 --> 00:12:44,547 smarter algorithm, which is still exponential in k that runs in time only 2 197 00:12:44,547 --> 00:12:46,042 to the k times the size of the graph.