English subtitles

← 07-07 Seed Problem

Get Embed Code
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,
  7. this work has already been done about 40 years ago
  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.