## ← 07-07 Seed Problem

• 1 Follower
• 39 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=J3REsSLc7Pw" data-team="udacity"></div> ``` 1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

1. So the big question is here,
2. how on earth are we going to do this?
3. Because this seems extremely difficult to show,
4. so we would have to find a problem for which we can
5. prove that any other problem in NP can be reduced to it.
6. Luckily for us or actually more luckily for me,
8. by showing a problem called Boolean
9. satisfiability, or SAT for short, to be NP-complete,
10. and this result is one of the most famous results in theoretical computer science,
11. which is why we're going to investigate it in detail
12. and also investigate the proof together.
13. The result is called the Cook-Levin theorem.
14. This theorem is named after Stephen Cook and Leonid Levin
15. who discovered it independently of each other in the 1970s,
16. and by showing that, they provided exactly this NP-complete seed problem,
17. namely SAT,
18. which could then be used to show that
19. a number of other problems are NP-complete as well.
20. And I'm then going to show you how Cook and Levin
21. proved that SAT is NP-complete,
22. and once we have shown that SAT is NP-complete,
23. we can go back to the problems of Alice, Bob, and Carol
24. and see if those problems are NP-complete.
25. Before we go deeper into the SAT problem and proving the Cook-Levin theorem,
26. here's one more quiz to make sure that you
27. understand where we are going with this.
28. So once we have shown that the SAT problem is NP-complete,
29. how would we then show, or at least try to show,
30. that the vertex cover problem, independent set, and clique are NP-complete?
31. Would we have to show that any input for SAT,
32. and I'll soon tell you what that input exactly is,
33. can be transformed into an input for one of these problems,
34. and by these problems, I mean vertex cover, independent set, or clique,
35. or would we have to show that one of the three problems up here
36. can be expressed as an input to SAT?
37. Or would we have to show that all three
38. problems can be expressed as an input to SAT?
39. So please check all of these which are correct.