0:00

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.

Â