
Title:
0707 Seed Problem

Description:

So the big question is here,

how on earth are we going to do this?

Because this seems extremely difficult to show,

so we would have to find a problem for which we can

prove that any other problem in NP can be reduced to it.

Luckily for us or actually more luckily for me,

this work has already been done about 40 years ago

by showing a problem called Boolean

satisfiability, or SAT for short, to be NPcomplete,

and this result is one of the most famous results in theoretical computer science,

which is why we're going to investigate it in detail

and also investigate the proof together.

The result is called the CookLevin theorem.

This theorem is named after Stephen Cook and Leonid Levin

who discovered it independently of each other in the 1970s,

and by showing that, they provided exactly this NPcomplete seed problem,

namely SAT,

which could then be used to show that

a number of other problems are NPcomplete as well.

And I'm then going to show you how Cook and Levin

proved that SAT is NPcomplete,

and once we have shown that SAT is NPcomplete,

we can go back to the problems of Alice, Bob, and Carol

and see if those problems are NPcomplete.

Before we go deeper into the SAT problem and proving the CookLevin theorem,

here's one more quiz to make sure that you

understand where we are going with this.

So once we have shown that the SAT problem is NPcomplete,

how would we then show, or at least try to show,

that the vertex cover problem, independent set, and clique are NPcomplete?

Would we have to show that any input for SAT,

and I'll soon tell you what that input exactly is,

can be transformed into an input for one of these problems,

and by these problems, I mean vertex cover, independent set, or clique,

or would we have to show that one of the three problems up here

can be expressed as an input to SAT?

Or would we have to show that all three

problems can be expressed as an input to SAT?

So please check all of these which are correct.