One of the most well known
decision problems is satisfiability. In
satisfiability we're given a boolean formula in conjunctive
normal form, and we're asking whether that formula has a
satisfying truth assignment. So here's what this means, like
what does the boolean formula in conjunctive normal form? Basically we have a number of
Boolean variables or their negations. We call a variable or
its negation literal. We then have clauses in the
formula. Each clause contains a number of literals which are
connected by a logic OR operation. So we have something
like x_1 or not x_2 or x_3. So that would be one example of a clause. And then the Boolean
formula is composed of such clauses which are connected
together by logical AND operations. So we say the
formula is true if all of the clauses are true. This is what conjunctive normal
form means. It's a conjunction of disjunctions of literals. As special case of
satisfiability is the problem 3SAT. 3SAT is the same as satisfiability but there's
an additional restriction on the input, namely that each clause
contains exactly 3 literals. So an example of the formula we
might have for 3SAT would be not x_1 or x_2 or x_3. That's
the first clause. And then and x_1 or not x_2
or x_3. This is the second clause. And then x_1 or
x_2 or x_3. That is the third clause, and not x_1 or not x_2 or not x_3.
That is the 4th clause. This formula has a satisfying
truth assignment. So we can find values for the variables in such
a way that the formula becomes true. In this case, we can set
x_1 to true or to 1. We can set x_2 to true as well
and we set x_3 to false or 0. Now, if you pluck these values
into the formula, we see that the first clause is satisfied
because x_2 is true, and x_2 appears in that clause. The second clause is satisfied
Becausw x_1 is true and x_1 appears in this clause. The third clause is satisfied
because both x_1 and x_2 appear in the clause and both of those
variables are true. And the last clause is also
satisfied. It's not satisfied because of x_1 or x_2 because
only not x_1 and not x_2 appear in the clause but not
x_3 appears in the clause and because x_3 is false, not
x_3 is true, and therefore the last clause is also
satisfies. It includes a true literal. Now this problem 3SAT
polynomial time Karp reduces to independent set. This is not obvious because
3SAT looks very different as a problem to independent
set, but we can do something that's called a gadget
construction to show this. So, given an input for 3SAT,
this is just a Boolean formula in CNF form. We construct a graph and a number k from this that
has the property that this graph has an independent set
of size at least k if and only if the formula has a
satisfying assignment. In constructions like this, what
you want to look for is what are the crucial properties of these problems. So in 3SAT,
one crucial part are the variables, right? So
variables can be true or false. And an independent set we also
make a choice. We make a choice to include a vertex in our
independent set or not. Therefore, we should consider
having vertices played the role of the literals in the formula. So this is what we're going to do. For each clause in the
3SAT formula, remember, a clause contains 3 literals, we create three
vertices for our graph. We then connect these three
vertices in a triangle. So we do this for each clause. And the idea here is that if we
want to pick something that is an independent set, we can pick
at most one of the vertices in each triangle. If you would pick
two vertices in a triangle they would be connected by an
edge and we would not have an independent set. So this forces
us to pick no more than a single vertex from each triangle, and
again each triangle stands for one clause in the formula. Next we want to ensure that the
choices of our selection are consistent. So for example, in
the first clause I have the variable x_2 and then in the
second clause I might have the negation of x_2. What I don't want to happen is
that we somehow select a vertex that belongs to x_2 and also
select a vertex that belongs to not x_2, because intuitively the
meaning of this would be that we set x_2 to true, but also set the
negation of x_2 to true at the same time. Of course, that's not
possible. So how can we enforce these consistent choices? When we pick our vertices for
our independent set. Well, we just connect x_2 and not
x_2 by an edge. So whenever we find a vertex
that corresponds to a variable and another vertex that
corresponds to the negation of that variable, we connect the
two by an edge. This ensures that our
choices are somewhat consistent. So when we
select vertices for our independent set, we make
choices that are consistent with assigning truth values
to the variables. This is the entire construction.
Now we need to think about what value for k we should choose. So
what should we demand and how large should our independent set be? If I want to satisfy the formula
Phi, how many clauses do I have to satisfy? This is exactly the
value for k that we should choose. So our k will be the
number of clauses in the formula. This ensures that if we
have an independent set, we pick at least k vertices, but we know
that we can pick at most one vertex from each triangle. So
now we know that in an independent set we must have
picked exactly one vertex in each triangle, because the number of
triangles is equal to the number of clauses in the formula. So now let's argue a little
bit more formally. Let S be an independent set of size
k in our constructed graph. As I said, S must contain
exactly one vertex in each triangle because there are
k triangles. Those vertices correspond to
some literals. If we select a vertex, we set the corresponding
literal to true. So this ensures that we have a
satisfying assignment, because indeed every clause now contains
a true literal. For the other direction, assume
that we are given a satisfying assignment for our formula. Then
I can find an independent set of size at least k. In the satisfying assignment,
each clause is true. So in each clause we can find a
literal that is true. We then just pick a vertex
that corresponds to that literal in the corresponding
triangle in the graph and include it in our independent
set. That is an independent set
of size k because we can pick a vertex from each
triangle because we can make each of the clauses
true if there is a satisfying assignment for
the formula Phi.