Showing Revision 3 created 05/25/2016 by Udacity Robot.

1. Title:
   SAT is NP-Hard - Intro to Algorithms
2. Description:

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