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
• 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
• 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