1 00:00:00,420 --> 00:00:03,040 In this video we'll begin our study of our final topic. 2 00:00:03,040 --> 00:00:07,020 First of all, what are NP complete for computational and tractable problems. 3 00:00:07,020 --> 00:00:09,810 And second of all, what are some good strategies for 4 00:00:09,810 --> 00:00:11,790 approaching them algorithmically. 5 00:00:11,790 --> 00:00:15,550 Let's begin by formally defining computational tractability 6 00:00:15,550 --> 00:00:17,670 via polynomial time solvability. 7 00:00:17,670 --> 00:00:19,880 That is where it define the complexity class p. 8 00:00:22,640 --> 00:00:26,260 As you know from the past several weeks of hard work, the focus of these design and 9 00:00:26,260 --> 00:00:30,460 analysis of evidence courses is to learn practical algorithms and 10 00:00:30,460 --> 00:00:34,050 relevant supporting theory for fundamental computational problems. 11 00:00:36,120 --> 00:00:39,850 By now, we have a very long list of such problems, sorting, searching, 12 00:00:39,850 --> 00:00:43,730 shortest path, minimum spanning trees, sequence alignment, and so on. 13 00:00:46,060 --> 00:00:49,030 But the sad fact is I've given you a quite biased sample 14 00:00:49,030 --> 00:00:51,230 thus far of computational problems. 15 00:00:51,230 --> 00:00:55,030 And for many important computational problems, including ones you are likely to 16 00:00:55,030 --> 00:01:00,120 run into in your own projects, there is no known efficient, 17 00:01:00,120 --> 00:01:03,830 let alone blazingly fast, algorithm for solving the problem. 18 00:01:06,010 --> 00:01:10,950 And as much as the focus of these courses is what you can do with algorithms rather 19 00:01:10,950 --> 00:01:15,220 than what you can't do, it would nevertheless be fraudulent, I think, 20 00:01:15,220 --> 00:01:19,930 to teach you about algorithms without discussing the spectre of intractability 21 00:01:19,930 --> 00:01:23,440 that haunts the professional algorithm designer and the serious programmer. 22 00:01:25,720 --> 00:01:29,020 In the same way your program or toolbox should include lots of different design 23 00:01:29,020 --> 00:01:32,680 paradigms like dynamic programming, greedy algorithms, divide and conquer, 24 00:01:32,680 --> 00:01:37,240 lots of different data structures, hash tables, balance search trees, and so on. 25 00:01:37,240 --> 00:01:39,940 That toolbox also should include 26 00:01:39,940 --> 00:01:44,840 the knowledge of computationally intractable that is mp complete problems. 27 00:01:44,840 --> 00:01:47,650 Maybe how to even establish problems are mp complete. 28 00:01:47,650 --> 00:01:53,420 Again this is because, these problems are likely to show up in your own projects. 29 00:01:53,420 --> 00:01:57,840 It is not uncommon that a graduate student at Stanford will come into my office 30 00:01:57,840 --> 00:02:01,920 asking for some advice, how to approach a problem that's come up in their own 31 00:02:01,920 --> 00:02:04,410 project from an algorithmic perspective. 32 00:02:04,410 --> 00:02:08,380 Very often, after they've sketched the problem for two minutes, five minutes on 33 00:02:08,380 --> 00:02:12,950 my white board, it's very easy to see that it is, in fact, an MP complete problem. 34 00:02:12,950 --> 00:02:16,780 They should not seek out a efficient exactly correct algorithm and 35 00:02:16,780 --> 00:02:19,350 instead they should resort to one of the strategies for 36 00:02:19,350 --> 00:02:22,170 dealing with MP complete problems that we'll be discussing later. 37 00:02:24,713 --> 00:02:28,603 So in the next sequence of videos my goal is to formalize the notion of 38 00:02:28,603 --> 00:02:33,113 computational intractability through the definition of NP completeness and 39 00:02:33,113 --> 00:02:35,179 also give you a couple of examples. 40 00:02:37,465 --> 00:02:40,765 The relatively brief discussion that I am going to give you of NP completeness 41 00:02:40,765 --> 00:02:44,755 is no substitute for a proper study of the topic, I encourage you to 42 00:02:44,755 --> 00:02:47,868 seek out a textbook or other free courses on the web to learn more. 43 00:02:47,868 --> 00:02:52,675 And indeed NP completeness I think is a topic worth learning at least 44 00:02:52,675 --> 00:02:56,062 twice from multiple different perspectives. 45 00:02:56,062 --> 00:02:59,385 And indeed those of you who have study it before I hope you find my treatment 46 00:02:59,385 --> 00:03:03,162 somewhat complementary to previous treatments that you might have seen. 47 00:03:03,162 --> 00:03:06,997 Indeed NP completeness is really one of the most famous important and 48 00:03:06,997 --> 00:03:11,707 influential exports from all of computer science to the broader scientific world. 49 00:03:13,750 --> 00:03:17,290 And as so many different disciplines are getting increasingly computational, and 50 00:03:17,290 --> 00:03:19,910 here I'm thinking of everything from the mathematical sciences 51 00:03:19,910 --> 00:03:22,820 to the natural sciences, even to the social sciences. 52 00:03:22,820 --> 00:03:25,820 These fields have really no choice but to confront and 53 00:03:25,820 --> 00:03:29,880 learn about NP completeness since it genuinely governs what can 54 00:03:29,880 --> 00:03:32,350 be accomplished computationally and what cannot. 55 00:03:34,410 --> 00:03:37,290 My perspective here will be unapologetically that of an algorithm 56 00:03:37,290 --> 00:03:37,830 designer. 57 00:03:37,830 --> 00:03:42,020 And in particular after our discussion of NP completeness, the rest of this course 58 00:03:42,020 --> 00:03:45,480 is going to focus on algorithmic approaches to these problems. 59 00:03:45,480 --> 00:03:48,809 If you're confronted with an NP complete problem, what should you do about it? 60 00:03:51,170 --> 00:03:54,720 So rather than starting out by formalizing computational intractability, 61 00:03:54,720 --> 00:03:58,640 it's a little simpler to begin by defining computation tractability. 62 00:04:00,790 --> 00:04:05,889 That brings us to the uber important definition of polynomial time solvability. 63 00:04:07,850 --> 00:04:11,780 So, the definitions of a mouthful, but it's exactly what you think it would be. 64 00:04:11,780 --> 00:04:14,310 So, the problem is polymer time solubility naturally 65 00:04:14,310 --> 00:04:17,230 if there's a polynomial algorithm that solves it. 66 00:04:17,230 --> 00:04:21,515 That is there's an algorithm and there's a constant K, so that if you feed in 67 00:04:21,515 --> 00:04:26,515 an input of length n to this algorithm then it will correctly solve the problem. 68 00:04:26,515 --> 00:04:27,985 Either it will correctly answer yes or no or 69 00:04:27,985 --> 00:04:31,015 it will correctly output an optimal solution, whatever. 70 00:04:31,015 --> 00:04:33,562 It correctly solves it in time, big o into the K. 71 00:04:33,562 --> 00:04:38,642 Pretty much all of the problems we've discussed it's been kind of 72 00:04:38,642 --> 00:04:40,824 obvious what the input length was. 73 00:04:40,824 --> 00:04:43,872 For example, the number of vertices plus the number of edges or 74 00:04:43,872 --> 00:04:46,982 it was the number of numbers that had to be sorted, etc. 75 00:04:46,982 --> 00:04:49,847 For abstract problem just informally I wouldn't 76 00:04:49,847 --> 00:04:53,332 encourage you to think about the input length, and as the number of keystrokes on 77 00:04:53,332 --> 00:04:56,779 the computer that would be required to describe that given instance. 78 00:04:59,020 --> 00:05:03,040 And yes it is true that strictly speaking to be polynomial time solvable all 79 00:05:03,040 --> 00:05:07,530 you need is a running tab of big N to the K for some constant K. 80 00:05:07,530 --> 00:05:12,671 Even if you get K = 10,000, that is enough to meet the demands of this definition. 81 00:05:12,671 --> 00:05:15,904 And of course for concrete problems you're going to see small values of K, 82 00:05:15,904 --> 00:05:18,350 in this course Ks usually been, one, two, or three. 83 00:05:20,510 --> 00:05:21,290 So a quick comment for 84 00:05:21,290 --> 00:05:23,400 those of you that are wondering about randomizing algorithms, and 85 00:05:23,400 --> 00:05:26,710 of course we saw some cool examples of randomized algorithms back in part one. 86 00:05:26,710 --> 00:05:29,500 So to keep the discussion simple, when we discuss computational 87 00:05:29,500 --> 00:05:32,580 intractability let's just think only about the deterministic algorithms. 88 00:05:32,580 --> 00:05:36,800 But at the same time, don't worry really all of the qualitative conclusions we're 89 00:05:36,800 --> 00:05:40,420 going to reach are believed to hold equally well for randomized algorithms. 90 00:05:40,420 --> 00:05:43,320 In particular we don't think that there are problems 91 00:05:43,320 --> 00:05:46,170 that deterministic algorithms require exponential time and yet 92 00:05:46,170 --> 00:05:49,240 randomization allows you to magically get polynomial time. 93 00:05:49,240 --> 00:05:52,920 There's even some mathematical evidence suggesting that is the case. 94 00:05:54,713 --> 00:05:59,190 So that brings us to the definition of the complexity class capital P. 95 00:05:59,190 --> 00:06:04,090 Capital P is just defined as the set of all polynomials times solvable problems. 96 00:06:04,090 --> 00:06:08,296 The set all problems that admits a polynomial time algorithm solving it. 97 00:06:10,673 --> 00:06:16,020 For those of you who have heard of the P verses NP question, this is the same P, 98 00:06:16,020 --> 00:06:21,915 throughout these courses we've exhibited many examples of problems in P, right? 99 00:06:21,915 --> 00:06:23,750 That's the whole meaning of the course. 100 00:06:23,750 --> 00:06:27,101 Sequence alignment, minimum cut, sorting, 101 00:06:27,101 --> 00:06:30,796 minimum expanding tree, shortest paths and so on. 102 00:06:33,005 --> 00:06:34,930 There are two exceptions. 103 00:06:34,930 --> 00:06:37,520 One we talked about exclusively at the time. 104 00:06:37,520 --> 00:06:41,830 Which we discussed the shortest paths in graphs with negative edge costs. 105 00:06:41,830 --> 00:06:45,890 And we stated that if you have negative cost cycles and 106 00:06:45,890 --> 00:06:49,740 you wanted shortest paths that are simple, that do not have any cycles in them. 107 00:06:49,740 --> 00:06:51,810 Then than turns out to be an NP complete problem. 108 00:06:51,810 --> 00:06:54,580 For those of you who that know about reductions an easy reduction 109 00:06:54,580 --> 00:06:55,980 from the Hamiltonian path problem. 110 00:06:58,190 --> 00:07:00,440 So we did not give a polynomial time algorithm for 111 00:07:00,440 --> 00:07:02,020 that version of the shortest path problem. 112 00:07:02,020 --> 00:07:02,850 We just punted on it. 113 00:07:04,870 --> 00:07:07,150 And the second example is a really subtle one. 114 00:07:07,150 --> 00:07:11,050 So, believe it or not we did not actually give a polynomial time algorithm for 115 00:07:11,050 --> 00:07:11,990 the knapsack problem. 116 00:07:13,710 --> 00:07:17,300 So, this requires an explication because at the time in our dynamic programming 117 00:07:17,300 --> 00:07:20,530 algorithm I'll bet it felt like it was a polynomial type algorithm. 118 00:07:20,530 --> 00:07:22,132 So, lets review what it's running time was. 119 00:07:22,132 --> 00:07:26,710 So, the knapsack problem the input is N items that have values and sizes. 120 00:07:26,710 --> 00:07:29,710 And also you're given this knapsack capacity, 121 00:07:29,710 --> 00:07:32,220 which is a positive integer capital W. 122 00:07:32,220 --> 00:07:35,640 And our table, our two dimensional array, had theta 123 00:07:35,640 --> 00:07:40,140 of N times capital W some problems, we spent constant time filling in each entry. 124 00:07:40,140 --> 00:07:43,857 So the running time of our dynamic programming algorithm was theta(n), 125 00:07:43,857 --> 00:07:47,046 the number of items, times capital W, the knapsack capacity. 126 00:07:49,210 --> 00:07:52,660 What on the other hand is the length of an instance of Knapsack? 127 00:07:52,660 --> 00:07:56,460 Well as we just said, the input to Knapsack is 2n plus 1 numbers. 128 00:07:56,460 --> 00:08:00,530 The end sizes, the end values, and the Knapsack capacity and 129 00:08:00,530 --> 00:08:03,816 naturally to write down any one of these numbers, 130 00:08:03,816 --> 00:08:07,587 you only need log of the magnitude of the number, right? 131 00:08:07,587 --> 00:08:10,205 So if you have an integer k and you want to write it in binary, 132 00:08:10,205 --> 00:08:11,710 that's log base 2 of k bits. 133 00:08:11,710 --> 00:08:14,450 If you want to write it down in base 10 digits, it's going to be log base 10 of K, 134 00:08:14,450 --> 00:08:17,460 which is the same up to a constant factor. 135 00:08:17,460 --> 00:08:22,517 So, the point is the input length is going to be proportional to N, and proportional 136 00:08:22,517 --> 00:08:26,880 to log of the magnitudes of the numbers, in particular log of capital W. 137 00:08:29,504 --> 00:08:33,195 So, here's another way to see why the dynamic programming algorithm is 138 00:08:33,195 --> 00:08:35,380 exponential in terms of the input length. 139 00:08:35,380 --> 00:08:36,910 Let me use an analogy. 140 00:08:36,910 --> 00:08:39,930 Suppose you were solving some problem over graph cuts. 141 00:08:39,930 --> 00:08:43,280 So remember, the number of cuts in a graph is exponential to the number of vertices. 142 00:08:43,280 --> 00:08:45,170 It's roughly two to the end for end vertices. 143 00:08:45,170 --> 00:08:49,380 So that means if you're brute force search and I add just one more vertex 144 00:08:49,380 --> 00:08:53,570 to the graph, it doubles the running time of your algorithm. 145 00:08:53,570 --> 00:08:55,280 That's exponential growth. 146 00:08:55,280 --> 00:08:58,540 But, actually the same thing is going on in the knapsack problem of the dynamic 147 00:08:58,540 --> 00:08:59,670 programming algorithm. 148 00:08:59,670 --> 00:09:02,480 Suppose you write everything in base ten and 149 00:09:02,480 --> 00:09:06,940 I just add one extra zero to the knapsack and passi, and multiply it by ten. 150 00:09:06,940 --> 00:09:09,600 Within the number of sure problems you have to solve goes up by ten. 151 00:09:09,600 --> 00:09:13,260 So, again I just added one digit, one keystroke to the input. 152 00:09:13,260 --> 00:09:17,620 And yes your running time got multiplied by a custom factor. 153 00:09:17,620 --> 00:09:22,390 So, it is again exponential growth with respect to the coding length of the input. 154 00:09:25,330 --> 00:09:27,790 Now it's no accident that we failed to get a poly time algorithm for 155 00:09:27,790 --> 00:09:29,290 the knapsack problem. 156 00:09:29,290 --> 00:09:31,690 Because that is in fact an NP complete problem. 157 00:09:31,690 --> 00:09:34,020 Again, we'll explain what NP complete means shortly. 158 00:09:36,150 --> 00:09:39,075 So that's the mathematical definition of the complexity class P, but 159 00:09:39,075 --> 00:09:42,375 more important than the math is the interpretation. 160 00:09:42,375 --> 00:09:45,005 That is how should you think about the class P. 161 00:09:45,005 --> 00:09:48,595 How should you think about polynomial time solvability. 162 00:09:48,595 --> 00:09:53,298 To the practicing algorithm design or the practicing programmer, membership in P, 163 00:09:53,298 --> 00:09:57,021 polynomial time solvability can be though of a rough litmus test for 164 00:09:57,021 --> 00:09:58,671 commutation tractability. 165 00:10:01,255 --> 00:10:06,087 Now, the identification of algorithms that run in big O (n to the k) time for some 166 00:10:06,087 --> 00:10:11,500 constant, k and practical computationally efficient algorithms is imperfect. 167 00:10:11,500 --> 00:10:15,320 There are of course, algorithms which in principle run in polynomial time but 168 00:10:15,320 --> 00:10:17,730 are too slow, to be useful in practice. 169 00:10:17,730 --> 00:10:21,660 Conversely, there are algorithms which are not polynomial time but 170 00:10:21,660 --> 00:10:22,760 are useful in practice. 171 00:10:22,760 --> 00:10:26,370 You already coded one up when you did the dynamic programming solution to knapsack, 172 00:10:26,370 --> 00:10:29,020 and we'll see several more examples in future lectures. 173 00:10:30,790 --> 00:10:35,140 And more generally, anyone who has the guts to write down a precise mathematical 174 00:10:35,140 --> 00:10:39,470 definition, like this complexity class P, needs to be ready for 175 00:10:39,470 --> 00:10:43,610 the inevitability that the definition will accommodate a few edge cases that you wish 176 00:10:43,610 --> 00:10:48,100 it didn't, and that it will exclude a few edge cases that you wish it didn't. 177 00:10:49,380 --> 00:10:53,720 This is an inevitable friction between the binary nature of mathematical properties 178 00:10:53,720 --> 00:10:56,780 and the fuzziness of reality. 179 00:10:56,780 --> 00:11:00,400 These edge cases are absolutely no excuse to ignore or 180 00:11:00,400 --> 00:11:04,695 dismiss a mathematical definition like this one, quite the contrary. 181 00:11:04,695 --> 00:11:08,785 The friction makes it that much more astonishing that you could write down 182 00:11:08,785 --> 00:11:12,675 a clean mathematical definition, something that either is satisfied or 183 00:11:12,675 --> 00:11:15,560 not satisfied by every single computational problem. 184 00:11:15,560 --> 00:11:20,260 And have it serve as such a useful guide to classify problems into 185 00:11:20,260 --> 00:11:24,460 the tractable in practice problems, and the intractable in practice problems. 186 00:11:24,460 --> 00:11:29,130 And we now have 40 yeas of experience that indicates this definition has been 187 00:11:29,130 --> 00:11:32,739 unreasonably effective in just that kind of classification. 188 00:11:35,740 --> 00:11:38,380 Generally speaking computational problems in 189 00:11:38,380 --> 00:11:41,290 P can be well solve using an off the shelf solutions. 190 00:11:41,290 --> 00:11:43,690 As we've seen of the many examples in this class. 191 00:11:45,200 --> 00:11:47,620 Problems that are believed not to be in P, 192 00:11:47,620 --> 00:11:51,219 generally requires significant computational resources, 193 00:11:51,219 --> 00:11:56,004 significant human resources and a lot of domain expertise to solve and practice. 194 00:12:01,504 --> 00:12:05,123 So we've mentioned in passing a couple of problems that are believed to not be 195 00:12:05,123 --> 00:12:06,720 polynomial time solvable. 196 00:12:06,720 --> 00:12:09,330 Let me pause here and tell you about a more famous one. 197 00:12:09,330 --> 00:12:10,711 The traveling salesman problem. 198 00:12:12,129 --> 00:12:16,264 The traveling salesman problem remarkably just doesn't sound that different than 199 00:12:16,264 --> 00:12:18,709 the minimum spanning tree problem, a problem for 200 00:12:18,709 --> 00:12:22,460 which we now know a litany of greedy algorithms that run in near linear time. 201 00:12:22,460 --> 00:12:25,520 So, the input is an undirected graph and let's go ahead and 202 00:12:25,520 --> 00:12:26,730 assume that it's a complete graph. 203 00:12:26,730 --> 00:12:30,964 So there's an edge between every pair of vertices every edge has a cost and 204 00:12:30,964 --> 00:12:35,420 the problem is nontrivial, even if every edge cost is just either one or two. 205 00:12:37,267 --> 00:12:40,837 Let me draw an example in green with four vertices. 206 00:12:50,296 --> 00:12:55,070 The responsibility of an algorithm for the TSP problem is to output the tour, 207 00:12:55,070 --> 00:12:59,210 that is a cycle that visits every single vortex exactly once. 208 00:12:59,210 --> 00:13:02,800 And amongst all tours, which you can think of as a permutation of the vertices, 209 00:13:02,800 --> 00:13:04,360 the order in which you visit them. 210 00:13:04,360 --> 00:13:07,295 You want the one that minimizes the sum of the edge costs. 211 00:13:08,506 --> 00:13:09,522 So for example, 212 00:13:09,522 --> 00:13:14,394 in the green graph that I've drawn, the minimum cost tour has total cost 13. 213 00:13:15,840 --> 00:13:17,960 So the TSP problem is simple enough to state. 214 00:13:17,960 --> 00:13:19,960 It's clear you could solve it by brute force search and 215 00:13:19,960 --> 00:13:24,200 roughly in factorial time just by trying all permutations of the vertices. 216 00:13:24,200 --> 00:13:25,470 But you know we see many, 217 00:13:25,470 --> 00:13:28,570 many examples in this class where you can do better than brute force search. 218 00:13:28,570 --> 00:13:31,540 And the TSP problem, people have been studying seriously, 219 00:13:31,540 --> 00:13:35,310 from a computational perspective, since at least the 1950s, 220 00:13:35,310 --> 00:13:39,300 including many huge names in optimization, people like George Danzig. 221 00:13:39,300 --> 00:13:43,560 So despite the interest over 60 years, there is, to date, 222 00:13:43,560 --> 00:13:47,820 no known polynomial time algorithm that solves the traveling salesman problem. 223 00:13:49,910 --> 00:13:52,800 In fact, way back in 1965, 224 00:13:52,800 --> 00:13:58,530 Jack Edmonds in a remarkable paper called Paths, Trees, and Flowers, conjectured 225 00:13:58,530 --> 00:14:03,370 that no polynomial time algorithm exists for the traveling salesman problem. 226 00:14:05,250 --> 00:14:10,080 This conjecture remains unresolved to this day, almost 50 years later. 227 00:14:10,080 --> 00:14:14,980 As we'll see, this is equivalent to the conjecture that P is not equal to NP. 228 00:14:14,980 --> 00:14:17,680 So, how would you formalize a proof of this conjecture? 229 00:14:17,680 --> 00:14:20,460 How would you amass evidence that this conjecture 230 00:14:20,460 --> 00:14:22,440 holds in the absence of a proof? 231 00:14:22,440 --> 00:14:25,379 Those are the topics of the upcoming videos.