1 00:00:00,012 --> 00:00:03,005 In this video, we'll begin our study of our final topic. 2 00:00:03,005 --> 00:00:07,415 First of all, what are NP-Complete, or computationally intractable problems. And 3 00:00:07,415 --> 00:00:10,905 second of all, what are some good strategies for approaching them 4 00:00:10,905 --> 00:00:13,632 algorithmically. Let's begin by formerly defining 5 00:00:13,632 --> 00:00:17,453 computational tractability via polynomial-time solvability, that is, 6 00:00:17,453 --> 00:00:19,996 we're going to define the complexity class P. 7 00:00:19,996 --> 00:00:25,126 As you know, from the past several weeks of hard work, the focus of these design 8 00:00:25,126 --> 00:00:30,588 and analysis of algorithms courses is to learn practical algorithms and relevant 9 00:00:30,588 --> 00:00:34,701 supporting theory for fundamental computational problems. 10 00:00:34,701 --> 00:00:39,903 By now, we have a very long list of such problems, sorting, searching, shortest 11 00:00:39,903 --> 00:00:43,972 path, minimum spanning trees, sequence alignment, and so on. 12 00:00:43,972 --> 00:00:48,397 But the sad fact is, I've given you a quite biased sample, thus far, of 13 00:00:48,397 --> 00:00:53,372 computational problems. And for many important computational problems, 14 00:00:53,372 --> 00:00:58,747 including ones you are likely to run into in your own projects, there is no known 15 00:00:58,747 --> 00:01:04,093 efficient, let alone blazingly fast algorithm for solving the problem. 16 00:01:04,093 --> 00:01:08,264 And, in as much as the focus of these courses is what you can do with 17 00:01:08,264 --> 00:01:13,218 algorithms rather than what you can't do. It would nevertheless be fraudulent, I 18 00:01:13,218 --> 00:01:17,660 think, to teach you about algorithms without discussing the specter of 19 00:01:17,660 --> 00:01:22,250 intractability that haunts the professional algorithm designer and the 20 00:01:22,250 --> 00:01:25,901 serious programmer. In the same way your program are toolbox, 21 00:01:25,901 --> 00:01:30,202 should include lots of different design paradigms like dynamic programming, 22 00:01:30,202 --> 00:01:34,700 greedy algorithms, divide and conquer, lots of different data structures, hash 23 00:01:34,700 --> 00:01:39,702 tables, balanced search trees and so on, that toolbox also should include the 24 00:01:39,702 --> 00:01:43,828 knowledge of computation intractable that is NP-Complete problems. 25 00:01:43,828 --> 00:01:47,070 Maybe even had to establish problem are NP-Complete. 26 00:01:47,070 --> 00:01:51,735 And again, this is because these problems are likely to show up in your own 27 00:01:51,735 --> 00:01:54,254 projects. It is not uncommon that a graduate 28 00:01:54,254 --> 00:01:58,560 student at Stanford will come into my office asking for some advice, how to 29 00:01:58,560 --> 00:02:02,729 approach a problem that's come up in their own project from an algorithmic 30 00:02:02,729 --> 00:02:05,657 perspective. Very often after they've sketched the 31 00:02:05,657 --> 00:02:10,214 problem for two minutes, five minutes, on my whiteboard it's very easy to see that 32 00:02:10,214 --> 00:02:14,213 it is in fact an NP-Complete problem. They should not seek out an efficient 33 00:02:14,213 --> 00:02:17,876 exactly correct algorithm and instead they should resort to one of the 34 00:02:17,876 --> 00:02:22,302 strategies for dealing with NP-Complete problems that we'll be discussing later. 35 00:02:22,302 --> 00:02:26,878 So in the next sequence of videos, my goal is to formalize the notion of 36 00:02:26,878 --> 00:02:32,312 computational intractability through the definition of NP-Completeness, and also 37 00:02:32,312 --> 00:02:36,957 give you a couple of examples. The relatively brief discussion that I'm 38 00:02:36,957 --> 00:02:41,843 going to give you of NP-Completeness is no substitute for a proper study of the 39 00:02:41,843 --> 00:02:44,951 topic. I encourage you to seek out a textbook or 40 00:02:44,951 --> 00:02:48,072 other free courses on the web to learn more. 41 00:02:48,072 --> 00:02:52,390 And indeed, NP-Completeness, I think, is a topic worth learning at least twice 42 00:02:52,390 --> 00:02:56,869 from multiple different perspectives. And indeed, those of you who have studied 43 00:02:56,869 --> 00:03:01,100 it before, I hope you find my treatment somewhat complementary to previous 44 00:03:01,100 --> 00:03:05,356 treatments that you might have seen. Indeed, NP-Completeness is one of the 45 00:03:05,356 --> 00:03:09,844 most famous, important, and influential exports from all of computer science to 46 00:03:09,844 --> 00:03:13,768 the broader scientific world. And as so many different disciplines are 47 00:03:13,768 --> 00:03:18,055 getting increasing computational, and here I'm thinking about everything from 48 00:03:18,055 --> 00:03:22,728 the mathematical sciences, to the natural sciences, even to the social sciences 49 00:03:22,728 --> 00:03:26,584 these fields have really no choice but to, confront and learn about 50 00:03:26,584 --> 00:03:30,281 NP-Completeness since it genuinely governs what can be accomplished 51 00:03:30,281 --> 00:03:33,913 computationally and what cannot. My perspective here will be 52 00:03:33,913 --> 00:03:36,524 unapologetically that of an algorithm designer. 53 00:03:36,524 --> 00:03:40,611 And in particular, after our discussion of NP-Completeness, the rest of this 54 00:03:40,611 --> 00:03:44,416 course is going to focus on algorithmic approaches to these problems. 55 00:03:44,416 --> 00:03:47,906 If you're confronted with an NP-Completeness problem, what should you 56 00:03:47,906 --> 00:03:53,007 do about it? So, rather than starting out by formalizing computational 57 00:03:53,007 --> 00:03:58,637 intractability, it's a little simpler to begin by defining computational 58 00:03:58,637 --> 00:04:02,517 tractability. That brings us to the uber important 59 00:04:02,517 --> 00:04:06,012 definition of polynomial-time solvability. 60 00:04:06,012 --> 00:04:10,207 So, the definition's a bit of a mouthful but it's sort of exactly what you think 61 00:04:10,207 --> 00:04:13,954 it would be. So, a problem is polynomial-time solvable, naturally, if 62 00:04:13,954 --> 00:04:16,764 there's a polynomial-time algorithm that solves it. 63 00:04:16,764 --> 00:04:21,009 That is, there's an algorithm and there's a constant k, so that if you feed in an 64 00:04:21,009 --> 00:04:25,179 input of length n to this algorithm, then it will correctly solve the problem. 65 00:04:25,179 --> 00:04:28,951 Either it will correctly answer yes or no, or it will correctly output an 66 00:04:28,951 --> 00:04:30,655 optimal solution. Whatever. 67 00:04:30,655 --> 00:04:35,547 Correctly solve them in time O(n^k). Pretty much all of the problems we have 68 00:04:35,547 --> 00:04:39,973 discussed it's been kind of obvious with the input length was, it was for example 69 00:04:39,973 --> 00:04:44,277 the number of vertices plus the number of edges, or it was the number of numbers 70 00:04:44,277 --> 00:04:47,713 that had to be sorted, etc. For an abstract problem, you know, just 71 00:04:47,713 --> 00:04:52,261 informally I would encourage you to think about the input length n as the number of 72 00:04:52,261 --> 00:04:57,637 key strokes on a computer that would be required to describe that given instance. 73 00:04:57,637 --> 00:05:02,116 And yes, it is true that strictly speaking to be polynomial-time solvable, 74 00:05:02,116 --> 00:05:07,398 all you need is a running time of O(n^k) for some constant k, even if you get k = 75 00:05:07,398 --> 00:05:11,115 10,000 that is enough to meet the demands of this definition. 76 00:05:11,115 --> 00:05:15,192 Of course, for concrete problems, you're going to see small values of k. 77 00:05:15,192 --> 00:05:17,783 In this course, k has usually been 1, 2, or 3. 78 00:05:18,802 --> 00:05:22,237 So, a quick comment for those of you that are wondering about randomized 79 00:05:22,237 --> 00:05:24,492 algorithms. And of course, we saw some cool examples 80 00:05:24,492 --> 00:05:27,977 of randomized algorithms back in Part I. So, to keep the discussion simple when we 81 00:05:27,977 --> 00:05:31,422 discuss computational intractability, let's just think only about deterministic 82 00:05:31,422 --> 00:05:33,567 algorithms. But at the same time, you know, don't 83 00:05:33,567 --> 00:05:36,742 worry, really. all of the qualitative conclusions we're 84 00:05:36,742 --> 00:05:40,267 going to reach are believed to hold equally well for randomized algorithms. 85 00:05:40,267 --> 00:05:43,667 In particular, we don't think that there are problems that deterministic 86 00:05:43,667 --> 00:05:47,617 algorithms require exponential time, and yet randomization allows you to magically 87 00:05:47,617 --> 00:05:51,242 get polynomial-time. There's even some mathematical evidence suggesting that 88 00:05:51,242 --> 00:05:55,094 that is the case. So that brings us to the definition of 89 00:05:55,094 --> 00:06:00,603 the complexity class, P. P is just defined as the set of all 90 00:06:00,603 --> 00:06:06,226 polynomials-time solvable problems. The set of all problems, that admits a 91 00:06:06,226 --> 00:06:11,981 polynomial-time algorithm solving it. For those of you who have heard of the P 92 00:06:11,981 --> 00:06:17,739 versus NP question, this is the same P. Throughout these courses, we've exhibited 93 00:06:17,739 --> 00:06:22,047 many examples of problems in P, right? That's really been sort of the 94 00:06:22,047 --> 00:06:26,468 whole point of the course. Sequence alignment, minimum cut, sorting, 95 00:06:26,468 --> 00:06:29,652 minimum spanning tree, shortest paths, and so on. 96 00:06:29,652 --> 00:06:33,742 There are two exceptions. One, we talked about explicitly at the 97 00:06:33,742 --> 00:06:38,995 time, which is when we discussed shortest paths in graphs with negative edge costs. 98 00:06:38,995 --> 00:06:43,747 And we stated that if you have negative cost cycles, and you wanted shortest 99 00:06:43,747 --> 00:06:48,549 paths that are simple, that do not have any cycles in them, then that turns out 100 00:06:48,549 --> 00:06:52,299 to be an NP-Complete problem. For those of you that know about 101 00:06:52,299 --> 00:06:56,763 reduction, it's an easier reduction from the Hamiltonian path problem. 102 00:06:56,763 --> 00:07:00,761 So, we did not give a polynomial-time algorithm for that version of the 103 00:07:00,761 --> 00:07:03,379 shortest path problem, we just punted on it. 104 00:07:03,379 --> 00:07:06,061 And the second example is a really subtle one. 105 00:07:06,061 --> 00:07:10,340 So, believe it or not, we did not actually give a polynomial-time algorithm 106 00:07:10,340 --> 00:07:14,441 for the knapsack problem. So, this requires an explanation because 107 00:07:14,441 --> 00:07:17,142 at the time, in our dynamic programming algorithm, 108 00:07:17,142 --> 00:07:19,950 I'll bet it felt like it was a polynomial-time algorithm. 109 00:07:19,950 --> 00:07:24,048 So, lets review what its running time was. So, in the knapsack problem, the 110 00:07:24,048 --> 00:07:26,432 input is n items that have values and sizes. 111 00:07:26,432 --> 00:07:31,175 And also you're given this knapsack capacity, which is the positive integer, 112 00:07:31,175 --> 00:07:33,781 W. And our table, our two dimensional array, 113 00:07:33,781 --> 00:07:38,641 had theta of n times W subproblems. We spent constant time filling in each 114 00:07:38,641 --> 00:07:41,008 entry. So the running time of our dynamic 115 00:07:41,008 --> 00:07:46,208 programming algorithm was theta of n, the number of items, times W, the knapsack 116 00:07:46,208 --> 00:07:49,635 capacity. What, on the other hand, is the length, 117 00:07:49,635 --> 00:07:55,835 of an instance of knapsack? Well, as we just said, the input to knapsack is 2n+1 118 00:07:55,835 --> 00:08:00,058 numbers, the n sizes, the n values, and the knapsack capacity. 119 00:08:00,058 --> 00:08:05,150 And, naturally, to write down any one of these numbers, you only need log of the 120 00:08:05,150 --> 00:08:09,163 magnitude of the number, right? So, if you have an integer k and you want to 121 00:08:09,163 --> 00:08:11,692 write it in binary, that's log base 2 of k bits. 122 00:08:11,692 --> 00:08:15,589 If you want to write it down in base 10 digits, it's going to be log base 10 of 123 00:08:15,589 --> 00:08:17,977 k, which is the same up to a constant factor. 124 00:08:17,977 --> 00:08:21,791 So, the point is, the input length is going to be proportional to n, and 125 00:08:21,791 --> 00:08:25,041 proportional to log of the magnitudes of the numbers. 126 00:08:25,041 --> 00:08:28,969 In particular, log of W. So, here's another way to see why the 127 00:08:28,969 --> 00:08:33,301 dynamic programming algorithm is exponential in terms of the input length. 128 00:08:33,301 --> 00:08:36,751 Let me use an analogy. Suppose you were solving some problem 129 00:08:36,751 --> 00:08:39,697 over graph cuts. So remember, the number of cuts in a 130 00:08:39,697 --> 00:08:43,701 graph is exponential to the number of vertices, it's roughly 2^n for n 131 00:08:43,701 --> 00:08:46,660 vertices. So that means if you're doing brute force 132 00:08:46,660 --> 00:08:51,345 search, and I add just one more vertex to the graph, it doubles the running time of 133 00:08:51,345 --> 00:08:53,762 your algorithm. That's exponential growth. 134 00:08:53,762 --> 00:08:57,997 But actually, the same thing is going on in the knapsack program with a dynamic 135 00:08:57,997 --> 00:09:01,544 programming algorithm. Suppose we write everything in base 10 136 00:09:01,544 --> 00:09:04,813 and I just add one extra zero to the knapsack capacity, 137 00:09:04,813 --> 00:09:08,427 I multiply it by 10. Well then, the number of sub-problems you 138 00:09:08,427 --> 00:09:12,205 have to solve goes up by 10. So again, I just added one digit, one 139 00:09:12,205 --> 00:09:16,050 keystroke to the input. And yet, your running time got multiplied 140 00:09:16,050 --> 00:09:19,639 by a constant factor. So, it is again, exponential growth with 141 00:09:19,639 --> 00:09:22,344 respect to the encoding length of the input. 142 00:09:22,344 --> 00:09:26,774 Now, it's no accident that we failed to get a polynomial time algorithm for the 143 00:09:26,774 --> 00:09:30,770 knapsack problem because that is, in fact an NP-Complete problem. 144 00:09:30,770 --> 00:09:34,108 And again, we'll explain what NP-Complete means shortly. 145 00:09:34,108 --> 00:09:38,203 So that's the mathematical definition of the complexity class, P. 146 00:09:38,203 --> 00:09:41,541 But more important than the math is the interpretation. 147 00:09:41,541 --> 00:09:44,346 That is, how should you think about the class P. 148 00:09:44,346 --> 00:09:48,250 How shold you think about polynomial, polynomial-time solveability. 149 00:09:48,250 --> 00:09:53,144 To the practicing algorithm designer, the practicing programmer, membership in P, 150 00:09:53,144 --> 00:09:57,131 polynomial-time solvability, can be thought as rough litmus test for 151 00:09:57,131 --> 00:10:01,439 computational tractability. Now, the identification of algorithms 152 00:10:01,439 --> 00:10:06,884 that run in big O(n^k) time for some constant k, and practical computationally 153 00:10:06,884 --> 00:10:11,824 efficient algorithms is imperfect. There are, of course, algorithms which in 154 00:10:11,824 --> 00:10:16,601 principle run in polynomial-time but are too slow to be useful in practice. 155 00:10:16,601 --> 00:10:21,788 Conversely, there are algorithms which are not polynomial-time but are useful in 156 00:10:21,788 --> 00:10:24,509 practice. You already coated one up when you did 157 00:10:24,509 --> 00:10:28,688 the dynamic programming solution in knapsack and we'll see several more 158 00:10:28,688 --> 00:10:32,661 examples in future lectures. And more generally, anyone who has the 159 00:10:32,661 --> 00:10:37,491 guts to write down a precise mathematical definition like this complexity class P, 160 00:10:37,491 --> 00:10:42,040 needs to be ready for the inevitability that the definition will accommodate a 161 00:10:42,040 --> 00:10:46,383 few edge cases that you wish it didn't and that it will exclude a few edge cases 162 00:10:46,383 --> 00:10:50,789 that you wish it didn't. This is an inevitable friction between 163 00:10:50,789 --> 00:10:55,633 the binary nature of mathematical properties and the fuzziness of reality. 164 00:10:55,633 --> 00:11:00,573 These edge cases are absolutely no excuse to ignore or dismiss a mathematical 165 00:11:00,573 --> 00:11:04,945 definition like this one. Quite the contrary, the friction makes it 166 00:11:04,945 --> 00:11:09,647 that much more astonishing that you could write down a clean mathematical 167 00:11:09,647 --> 00:11:13,182 definition. Something that either is satisfied or not 168 00:11:13,182 --> 00:11:17,692 satisfied to every single computational problem and have it served as such a 169 00:11:17,692 --> 00:11:22,282 useful guide to classify problems into the tractable in practice problems and 170 00:11:22,282 --> 00:11:26,857 the intractable in practice problems. We now have 40 years of experience that 171 00:11:26,857 --> 00:11:31,974 indicates this definition has been unreasonably effective in just that kind 172 00:11:31,974 --> 00:11:35,893 of classification. Generally speaking, computational 173 00:11:35,893 --> 00:11:41,285 problems in P can be well solved using off the shelf solutions, as we've seen in 174 00:11:41,285 --> 00:11:46,262 the many examples in this class. Problems that are believed not to be in 175 00:11:46,262 --> 00:11:51,401 P, generally require significant computational resources, significant 176 00:11:51,401 --> 00:11:55,687 human resources, and a lot of domain expertise to solve in practice. 177 00:11:55,687 --> 00:12:02,012 So, we've mentioned in passing a couple of problems that are believed to not be 178 00:12:02,012 --> 00:12:06,877 polynomial-time solvable. Let me pause here and tell you about a 179 00:12:06,877 --> 00:12:10,652 more famous one, the traveling salesman problem. 180 00:12:10,652 --> 00:12:14,937 The traveling salesman problem remarkably just doesn't sound that different than 181 00:12:14,937 --> 00:12:18,857 the minimum spanning tree problem. A problem for which we now know a litany of 182 00:12:18,857 --> 00:12:22,752 greedy algorithms that run in near linear time. So, the input is an undirected 183 00:12:22,752 --> 00:12:26,942 graph, and let's go ahead and assume that it's a complete graph, so there's an edge 184 00:12:26,942 --> 00:12:32,019 between every pair of vertices. Every edge has a cost and the problem is 185 00:12:32,019 --> 00:12:36,447 non-trivial even if every edge cost is either one or two. 186 00:12:36,447 --> 00:12:40,562 Let me draw an example in green with four vertices. 187 00:12:40,562 --> 00:12:50,609 The responsibility of an algorithm for the TSP problem is to output a tour, 188 00:12:50,609 --> 00:12:58,372 that is a cycle that visits every single vertex exactly once. 189 00:12:58,372 --> 00:13:02,387 And amongst all tours, which you can think of as a permutation of the 190 00:13:02,387 --> 00:13:07,102 vertices, the order in which you visit them, you want the one that minimizes the 191 00:13:07,102 --> 00:13:10,727 sum of the edge costs. So, for example, in the green graph that 192 00:13:10,727 --> 00:13:14,022 I've drawn, the minimum cost tour has total cost 13. 193 00:13:14,022 --> 00:13:17,741 So, the TSP problem is simple enough to state, it's clear you can solve it by 194 00:13:17,741 --> 00:13:21,173 brute force search and roughly n-factorial times, just by trying all 195 00:13:21,173 --> 00:13:24,626 permutations of the vertices. But you know, we've seen many, many 196 00:13:24,626 --> 00:13:28,162 examples in this class where you can do better than brute force search. 197 00:13:28,162 --> 00:13:32,322 And, the TSP problem, people have been studying seriously, from a computational 198 00:13:32,322 --> 00:13:36,573 Perspective since at least the 1950's, including many huge names in 199 00:13:36,573 --> 00:13:41,776 optimization, people like George Danzik. So, despite the interest over 60 years, 200 00:13:41,776 --> 00:13:46,908 there is to date no known polynomial-time algorithm that solves the traveling 201 00:13:46,908 --> 00:13:48,518 sales. The problem. 202 00:13:48,518 --> 00:13:55,065 In fact, way back in 1965, Jack Edmonds, in a remarkable paper called Paths, Trees 203 00:13:55,065 --> 00:14:00,982 and Flowers, conjectured that no polynomial-time algorithm exists for the 204 00:14:00,982 --> 00:14:06,571 travelling salesman problem. This conjecture remains unresolved to 205 00:14:06,571 --> 00:14:10,993 this day, almost 50 years later. As we'll see, this is equivalent to the 206 00:14:10,993 --> 00:14:15,774 conjecture that P is not equal to NP. So, how would you formalize a proof of 207 00:14:15,774 --> 00:14:19,361 this conjecture? How would you amass evidence that this 208 00:14:19,361 --> 00:14:22,142 conjecture holds in the absence of a proof? 209 00:14:22,142 --> 00:14:22,998 Those are the topics of the upcoming videos.