So, for those of you out there that fancy yourself computer scientists, I hope you feel some pride seeing this definition. I mean, how cool is it that our discipline came up with such a great concept of an NP-complete problem? The fact that there's a universal problem that simultaneously encodes all computational problems in which you can efficiently recognize a solution. There remains, however, a niggling issue. In general, when you're confronted with a mathematical definition, like the definition of NP-completeness that I just gave you, you should demand two things. The first thing you should demand is an explanation of why you should care. That is, if the definition is met, if satisfied, what are the interesting consequences. I'd like to think I've given you a very satisfying answer of that question for the definition of NP-completeness. I've argued that if a problem is NP-complete, then that's strong evidence of computational interactability. In the sense that polynomial-time algorithm for this NP-complete problem, if one hypothetically existed, that would automatically solve efficiently thousands of fundamental computational problems, anything for which you can efficiently recognize solution. But, the second thing you should demand from somebody who offers you a mathematical definition is examples. Do things that I care about actually meet this definition? And NP-completeness, I haven't shown you anything. And indeed, when you look at this interpretation, a single problem that simultaneously is encoding all problems with efficiently recognizable solutions. You might well wonder, could such objects ever exist? And the reason the theory of NP-completeness is so powerful, and over the past 40 years has been exported from computer science to all kinds of other disciplines is that, that question also has an incredibly satisfying answer. It turns out, tons of problems are not merely in NP. They don't merely have officially recognizable solution. Thousands and thousands of problems are in fact, NP-complete as hard as any other problems in NP. So, both the definition of NP-completeness and the facts that amazingly there exist NP-complete problems, that's due to independently Steve Cook and Leonid Levin. So, Cook and Levin came up with their largely similar theories independently. Cook was at that time as he is today, at the University of Toronto. Leonid Levin was behind the Iron Curtain, so he was working in the Soviet Union. So, it took awhile before his results were known in the West. These days, Levin is a professor at Boston University. Both Cook and Levin proved not just the basic existence result, but also gave some hints that problems that people really care about are also going to be NP-complete. For example, some constraint satisfaction problems like 3 snaps. But the vast scope of NP-completeness, the sheer breadth of problems that would eventually be proven NP-complete, was first made clear in a 1972 paper by Richard Karp. In that paper, he showed 21 different problems are NP-complete, including the traveling salesman problem, and various problems that many different communities had been stuck on for decades. And now, became clear that NP-completeness was the fundamental obstacle preventing progress in efficient algorithm across many, many domains. So, another thing that's amazing about NP-completeness, and a big reason for why it's been so successfully exported from, first of all, theoretical computer science to computer science more broadly, and then beyond into engineering and the other sciences, is that it's quite easy to stand on the shoulders of these giants and prove that new problems, problems that you care about, are also NP-complete. So, imagine that there is some computational problem pi that you really care about. This is just crucial to the project that you're working on, and you're stuck. You've been trying for weeks to solve it, throwing everything in your tool box added. You tried greedy algorithms, divide and conquer, dynamic programming, randomization. You've thrown every data structure in the book out of hash tables, heap search trees. Nothing works. You can't come up with an efficient algorithm. At that point, you should contemplate the possibility that the issue is not your own lack of cleverness or ingenuity. The issue is not having few, too few tools in your programmer toolbox. Perhaps, the issue is intractability of the computational problem that you're trying to solve. So, when you reach this point of exasperation, it's time to consider applying the following 2-step recipe, for establishing that the problem pi is NP-complete. Of course, the problem doesn't go, go away just because you prove it's NP-complete, but you should approach it using a different algorithmic strategy. And we'll discuss some of the most popular such strategies of approaching NP-complete problems in the rest of this course. So, let me state the 2-step recipe just at a, at a very high level. So, the first thing you need to do is settle on a suitable choice of an NP-complete problem, pi prime. The second thing you need to do is you need to show that pi prime reduces to the problem you care about pi. That shows that your problem is at least as hard as this NP-complete problem, in the sense that the NP-complete problem reduces to yours. And therefore, your problem, assuming it's an NP, is NP-complete as well. So clearly, the devil is in the details of successfully executing this 2-step recipe. And you might well be wondering, well, how on Earth do I know which NP-complete problem pi prime I should use? And then secondly, how am I going to come up with this reduction from this NP-complete problem pi prime, to my own problem pi? But, don't be intimidated by either of these two steps. With just a little bit of practice, you can actually get quite good at both of these steps and execute this recipe successfully in a lot of different cases. So, one thing that should make the first step less intimidating is there are some excellent lists of NP-complete problems. In particular, simple ones that tend to be useful in devising your own reductions. And the canonical such list is the book by Garey and Johnson called Computers and Intractability. It's from 1979, but it's still incredibly useful. I don't think I know of another Computer Science book that's more than 30 years old which is as useful as this one. So, there still remains the question of how you actually come up with one of these reductions from a known NP-complete problem pi prime to the problem you actually you care about, pi. But, don't be intimidated by this step either. So, first of all, as an algorithms person, you should be thinking about reductions all the time, anyways. You should be a very natural note of thought for you. For example, when we first started talking about all pair of shortest paths, we quickly observed that it reduces to the single shortest path problem. So, that mentality of, of solving one problem using another is equally useful in the design of NP-completeness reductions. And also, there's a lot of resources available to gain facility with NP-completeness reductions. You can look into various algorithms textbooks. Generally, they have lots of examples. The Garey & Johnson book is a good one. There are some online courses that study NP-completeness in more depth. Those resources will give you a lot of examples of NP-completeness reductions. It'll offer some tips on how to come up with them yourself and, most importantly, practice will make perfect. So, I strongly encourage you to take advantage of those resources. I think you'll be pleased to have NP-completeness as part of your toolbox. Certainly, nobody wins if you spend weeks or months of your life in inadvertently trying to prove that P=NP.