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.