1
00:00:00,000 --> 00:00:02,000
I mentioned NP hardness before.
2
00:00:02,000 --> 00:00:07,000
Now that we've talked about reduction, we can revisit that definition and say--
3
00:00:07,000 --> 00:00:13,000
a problem X is NP hard if we can reduce some other NP hard problem to it,
4
00:00:13,000 --> 00:00:19,000
what that really means is we can use a solution to problem X to solve some NP hard problem,
5
00:00:19,000 --> 00:00:23,000
that means that solving X has to be at least as hard as the NP hard problem
6
00:00:23,000 --> 00:00:25,000
making it therefore NP hard.
7
00:00:25,000 --> 00:00:31,000
Now, there's something sort of irritatingly circular or turtles all the way downish about this.
8
00:00:31,000 --> 00:00:35,000
We want to show that some problems in NP hard we got some problem,
9
00:00:35,000 --> 00:00:39,000
we have to show that we can reduce some other NP hard problem to it.
10
00:00:39,000 --> 00:00:43,000
We need that problem to be NP hard. How do we show that that problem is NP hard.
11
00:00:43,000 --> 00:00:47,000
Well, we can just show that there're some other NP hard problems that we could reduce to it
12
00:00:47,000 --> 00:00:52,000
and so on and so on and so on, and it doesn't really seem like we could ever get anywhere this way.
13
00:00:52,000 --> 00:01:00,000
But the good news is that back in 1971, Stephen Cook gave essentially the original NP hard problem
14
00:01:00,000 --> 00:01:02,000
and that is SAT, so SAT we know is NP hard.
15
00:01:02,000 --> 00:01:08,000
And the way that he showed that is really ingenious, he actually showed that if you had
16
00:01:08,000 --> 00:01:12,000
something that could solve SAT, you could use it to simulate in polynomial time,
17
00:01:12,000 --> 00:01:14,000
essentially an NP computer--right.
18
00:01:14,000 --> 00:01:18,000
A computer that makes these non-deterministic choices, and since that's the case,
19
00:01:18,000 --> 00:01:22,000
anything that we could run on an NP computer, we can turn into a SAT problem
20
00:01:22,000 --> 00:01:26,000
and therefore, SAT is as hard as anything in NP, so that's great.
21
00:01:26,000 --> 00:01:29,000
Cook got us off the ground here by giving an NP hard problem.
22
00:01:29,000 --> 00:01:31,000
Now we have something else to target.
23
00:01:31,000 --> 00:01:34,000
We have some other way if we want to start that some problems are NP hard.
24
00:01:34,000 --> 00:01:39,000
We can just reduce SAT to it and then we're done, but at this point now,
25
00:01:39,000 --> 00:01:43,000
there's actually a huge number of problems that are known to be NP hard.
26
00:01:43,000 --> 00:01:48,000
If you encounter a new problem, it may already be known to be NP hard or it may very well be
27
00:01:48,000 --> 00:01:51,000
that some know NP hard problem can be reduced to it,
28
00:01:51,000 --> 00:01:55,000
so you don't necessarily have to go all the way to SAT to do it.