
Now back to our initial question.

What does all of this mean for Alice, Bob, and Carol?

We have already seen that

the problems they are trying to solve are contained in NP

and so what we could now try is

to show that their problems are actually

NP complete.

To do that, what we need to do is

we need to reduce SAT

to one of their problems,

and we're going to do this with clique.

It's also possible to do this with vertex cover or independent set,

but clique is actually one of the easier ones to see.

And now what we need to show is

for any given instance of SAT,

so for any Boolean formula, if you will,

we can transform it

into an input for the clique problem

in polynomial time such that clique

as a decision problem will say yes

if the Boolean formula has a satisfying assignment

and no otherwise,

and once we achieve this, we know that clique is NP complete

and since we have already seen there are polynomial time reductions

between clique, vertex, and independent set,

if clique is NP complete,

then these 2 problems here are also NP complete

which of course will mean that

not only will Bob be very unhappy about this,

but Alice and Carol will be in this together, as well.