Return to Video

09-05 What Does This Mean For Alice

  • 0:00 - 0:03
    Now back to our initial question.
  • 0:03 - 0:07
    What does all of this mean for Alice, Bob, and Carol?
  • 0:07 - 0:09
    We have already seen that
  • 0:09 - 0:12
    the problems they are trying to solve are contained in NP
  • 0:12 - 0:15
    and so what we could now try is
  • 0:15 - 0:17
    to show that their problems are actually
  • 0:17 - 0:19
    NP complete.
  • 0:19 - 0:21
    To do that, what we need to do is
  • 0:21 - 0:24
    we need to reduce SAT
  • 0:24 - 0:26
    to one of their problems,
  • 0:26 - 0:28
    and we're going to do this with clique.
  • 0:28 - 0:32
    It's also possible to do this with vertex cover or independent set,
  • 0:32 - 0:35
    but clique is actually one of the easier ones to see.
  • 0:35 - 0:37
    And now what we need to show is
  • 0:37 - 0:39
    for any given instance of SAT,
  • 0:39 - 0:42
    so for any Boolean formula, if you will,
  • 0:42 - 0:43
    we can transform it
  • 0:43 - 0:46
    into an input for the clique problem
  • 0:46 - 0:49
    in polynomial time such that clique
  • 0:49 - 0:51
    as a decision problem will say yes
  • 0:51 - 0:53
    if the Boolean formula has a satisfying assignment
  • 0:53 - 0:55
    and no otherwise,
  • 0:55 - 0:58
    and once we achieve this, we know that clique is NP complete
  • 0:58 - 1:02
    and since we have already seen there are polynomial time reductions
  • 1:02 - 1:04
    between clique, vertex, and independent set,
  • 1:04 - 1:05
    if clique is NP complete,
  • 1:05 - 1:08
    then these 2 problems here are also NP complete
  • 1:08 - 1:09
    which of course will mean that
  • 1:09 - 1:11
    not only will Bob be very unhappy about this,
  • 1:11 -
    but Alice and Carol will be in this together, as well.
Title:
09-05 What Does This Mean For Alice
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
01:16
Amara Bot added a translation

English subtitles

Revisions