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.