English subtitles

← 07-08 Seed Problem

Get Embed Code
1 Language

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

  1. And this time we only have one correct answer,
  2. which is this one up here.
  3. So once we know that SAT is NP-complete
  4. and we wanted to show that those three problems,
  5. vertex cover, independent SET, and clique are NP-complete as well,
  6. we would have to show that if we take any input for SAT,
  7. then we can transform it into one of
  8. those three problems up here and then solve that.
  9. Because that shows us that in a way vertex cover or independent SET
  10. or clique are at least as hard to solve as SAT.
  11. And because SAT is NP-complete,
  12. if one of these problems is at least as hard to solve,
  13. then that problem must be NP-complete as well.
  14. These two down here are the wrong way around
  15. because SAT is NP-complete,
  16. which means that this is one of the
  17. hardest problems that you will find in NP,
  18. so just showing that for example,
  19. you could take vertex cover and transform it into an input for SAT
  20. would only show you that SAT is at least as hard to solve as vertex cover,
  21. but that is the wrong way around,
  22. because we want to show that vertex cover is at least as hard to solve as SAT,
  23. so those two answers down here are not correct.