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.

Definition and Interpretation of NP-Completeness II

Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

Meet the Instructors