English subtitles

← 09-05 What Does This Mean For Alice

Get Embed Code
1 Language

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

  1. Now back to our initial question.
  2. What does all of this mean for Alice, Bob, and Carol?
  3. We have already seen that
  4. the problems they are trying to solve are contained in NP
  5. and so what we could now try is
  6. to show that their problems are actually
  7. NP complete.
  8. To do that, what we need to do is
  9. we need to reduce SAT
  10. to one of their problems,
  11. and we're going to do this with clique.
  12. It's also possible to do this with vertex cover or independent set,
  13. but clique is actually one of the easier ones to see.
  14. And now what we need to show is
  15. for any given instance of SAT,
  16. so for any Boolean formula, if you will,
  17. we can transform it
  18. into an input for the clique problem
  19. in polynomial time such that clique
  20. as a decision problem will say yes
  21. if the Boolean formula has a satisfying assignment
  22. and no otherwise,
  23. and once we achieve this, we know that clique is NP complete
  24. and since we have already seen there are polynomial time reductions
  25. between clique, vertex, and independent set,
  26. if clique is NP complete,
  27. then these 2 problems here are also NP complete
  28. which of course will mean that
  29. not only will Bob be very unhappy about this,
  30. but Alice and Carol will be in this together, as well.