0:00

We now come to a more interesting reduction that connects Boolean logic

Â to graphs.

Â Namely we are going to reduce this 3-SAT [INAUDIBLE] problem,

Â there is an independent set problem.

Â Recall that in the 3-SAT problem,

Â our input is a formula in 3-CNF, that is a collection of clauses.

Â Each clause is a disjunction of at most three literals.

Â And our goal is to check whether it is possible to assign Boolean values

Â to all the variables of the formula F, so that to satisfy all the given clauses.

Â 0:40

Since we need to reduce this to the independent set problem our goal

Â is to polynomial logarithm that takes the formula F in 3-CNF.

Â And outputs a graph G and an integer b such that

Â the input formula F is satisfiable, if and only if,

Â there is an independent set of size at least b in the graph G.

Â 1:25

The given example, consider the following formula.

Â It is satisfied by an assignment which assigns the value true as value 1 to

Â all the variables.

Â Indeed, in the first clause we have just all

Â the literals in the first clause are satisfied.

Â In the second clause, the first literal is satisfied by this truth assignment.

Â And in the last clause,

Â the first literal is also satisfied by this truth assignment.

Â 1:54

Then with another assignment that satisfies the same formula,

Â namely if I assign the value 1 to x and the value 0 to y and z.

Â We satisfy the first literal in the first clause,

Â we satisfy both literals in the second clause, and

Â we satisfy the last literal in the last clause.

Â This point of view gives us an alternative definition of the satisfiability problem.

Â Namely to satisfy a given CNF formula, we need to select from each clause

Â of a given formula one literal, such as the resulting said of selected.

Â Literals is consistent, meaning that it doesn't contain a literal L,

Â together with its negation.

Â Let me illustrate this on a toy example, as usual.

Â Assume that we have a formula consistent of three clauses over variables x,

Â y, and z.

Â Well by consistent set of literals in this case, we mean for example x, x and not z.

Â 2:59

So this is one, so from first clause we select the literal x, from the second one

Â we also select the literal x, and from the third clause we select the literal not z.

Â Note that for these consistent set of literals,

Â we can find the corresponding satisfying assignment.

Â Namely, we assign value 1 to x, and the value 0 to z.

Â Namely, we satisfy all the literal in this set.

Â So for this we assign the value 1 to x and value 0 to z.

Â It is easy to see that this is indeed a satisfying assignment.

Â So in the first clause x is satisfied on the second clause,

Â x is satisfied on the last clause not z inside this fight.

Â It was the value of y doesn't actually matter in this case.

Â We can get a the full consistent set of literal just by selecting x and

Â from the first clause x from the second clause, and y from the third clause.

Â 4:04

And as a possibility is to select x from the first one,

Â not y from the second one and not z from the third one.

Â This will give us the following constant set of literals.

Â Once again, we want this set of literals to be consistent so

Â that we are able to assign a specific value for reach literal.

Â So for this, to explain this better

Â let's consider some inconsistent sets of literals.

Â Assume that from the first clause we select not y,

Â from the second clause we select the negation of y from the second,

Â from the third clause we select not z.

Â So this gives us the following set of literals,

Â which is inconsistent because It contains was y and a negation of y.

Â In this case, we can not assign

Â the value to y to satisfy all the laterals in this clause.

Â Namely if we assigns a value 0 to y, then we falsify this literal y.

Â If we assign the value 1 to y, we falsify this literal in this clause.

Â And this is exactly the reason why we would like our set of selected literals

Â to be consistent.

Â This alternative statement of the satisfiability problem is the main idea,

Â is the main ingredient of our reduction from 3-SAT to

Â the independent set problem problem.

Â We illustrate the reduction first on a toy example as usual.

Â Given a formula in this case with five clauses,

Â so with three variables, x y and z.

Â The first step is to introduce for each clause two or

Â three new vertices labeled with the literals of this clause.

Â In this case, it gives us the following picture.

Â So x, y and z here correspond to this clause.

Â 5:58

X and not y here respond to this clause the last

Â three vertices to respond to this clause and so on.

Â The next thing to do is to join all the vertices,

Â all the pairs of vertices inside each block.

Â So for those three clauses, we have two triangles and

Â for those two clauses, we have just three edges.

Â 6:25

Once again, each three clause corresponds to a triangle,

Â each two clause, that is clause of length two corresponds to a single edge.

Â So all these edges actually, what am I going to do,

Â is to find a large independent set in this graph.

Â And all the newly added edges force us to

Â select into our independent set at most one vertex from each block.

Â For example we cannot select two vertices from this block you aren't

Â doing independent set because any two of them are joined by an edge.

Â The same is for this block, for example.

Â We can only select just one vertex from this block into an independent set,

Â because they are connected by en edge.

Â 7:14

So selecting a vertex from each of these blocks into an independent set,

Â corresponds to selecting a literal from the corresponding clause,

Â that is going to be satisfied in this clause.

Â We call that in each clause we need to select a literal which is going to satisfy

Â this clause.

Â So we mimic this by selecting the corresponding vertex from a block.

Â However, recall that we need to select a consistent set of literals.

Â That is we do not want to select for example,

Â was x from some clause and not x from some other clause.

Â To force our set of selected vertices to

Â be labeled with consistent set of literals,

Â we just add all possible edges between all pairs of complementary literals.

Â Namely, whenever we have a vertex labeled with x like this one, and

Â not x kike this one, we join them by an edge.

Â So we have x here, we have not x here, we join them by an edge.

Â Another pair of vertices x here and not x here.

Â We also join them by an edge, then there is another vertex labeled by x,

Â we'll also join them by an edge, x and not x and z this not x.

Â And we do this for all of the pairs of complementary literals.

Â Now, the claim is that this graph contains an independent set of sides.

Â Exactly 5 or at least 5 if and only if the initial formula is satisfiable.

Â 8:55

And it is already clear, so if the formula is satisfiable,

Â this means that for each clause we can select one literal

Â such that the resulting set of literals is consistent.

Â But this also means that from each of these five block, so

Â this is the first block, corresponding to the first block, this is the second,

Â this is the third one, this is the fourth one, this is the fifth one.

Â We can select exactly the same vertex that corresponds to the selected

Â literal in this formula.

Â So if the formula is satisfiable, then in each block we can select on vertex.

Â And we know that they are not going to be joined by edges,

Â because vertices from different blocks are only joined if they are complementary.

Â And we know that our set of literals does not contain complimentary literals.

Â So if the formula is satisfiable,

Â then this graph contains an independent set of size 5.

Â And vice versa uses graph contents an independent set of size 5 and

Â the formula is satisfied both.

Â Why is that?

Â Well just because any independent set of size 5

Â has exactly 1 various of nature of these blocks.

Â And we know that the labels of these vertices give us a set of

Â literals which is consistent, which doesn't contain

Â a literal together with it's complementary literal.

Â So it gives us a set of literals such that it

Â intersects every clause of our initial formula.

Â Which means that if the response,

Â they are satisfying the assignment of the initial formula.

Â To summarize, let's state this reduction formally.

Â The reduction works as follows, given formula F in 3-CNF, that is

Â a collection of clauses, each of length at most three, what is the following?

Â We scan the set of the clauses from left to right and

Â for each clause, we introduce three or two,

Â or just one dependent on the number of literals in this clause.

Â Three or two, or one vertices, and we'll label them with

Â literals of this clause and we join every two of them by an edge.

Â So we are now constructing a graph G, and

Â this forces every independent set in this graph to contain

Â at most one vertex from each block to responding to a single clause.

Â 11:31

Then we also need to force each independent set to be labeled with

Â a set of literals which is consist.

Â For this we do the following, we join every pair of vertices

Â in our graph which are labeled with complementary literals.

Â That is if I got axis labeled with a literal L, we add new addresses

Â that connect it to all vertices, which are labeled with a negation of L.

Â Then what we've just proved on it, our example is the following.

Â The resulting graph G contains an independent set of size B,

Â where B is the number of clauses of the initial formula

Â even though with the initial formula is satisfiable.

Â 12:22

It remains to note that the running time of

Â the resulting transformation is polynomial.

Â Why is that?

Â Well just because to construct this graph we first just

Â scan the formula which takes linear time on the size of the formula.

Â It is just big O of the number of clauses,

Â to make it more formal let's denote by m the number of clauses and

Â in our formula then this step takes time O(m).

Â We just count the list of clauses and during this scan we introduce 3m vertices.

Â And then we need to check every pair of these vertices and to join them by

Â intersect if they're labeled by a complimentary pair of literals.

Â So the second step clearly takes time at most m squared.

Â In any case, this is polynomial so the wall transformation takes polynomial time.

Â Formally, we need also to describe an algorithm that transforms

Â any solution to the maximum independent set problem for

Â the resulting graph back to a solution to the three satisfiability problem.

Â And we also need to ensure that if there is no solution for

Â the resulting instance of the maximum independent set problems,

Â then there is no solution for the initial problem.

Â But this is not difficult, and we did this already.

Â Namely, if there is a solution for the resulting

Â instance of the maximum independent set problem and there is a maximum,

Â there is an independent set of size equal to the number of clauses.

Â That means that from each block we can select a vertex,

Â such that all the labels of these vertices is consistent.

Â If the consistent set of literals, but this also means that this gives

Â the satisfying assignment of the initial formula.

Â 14:21

If on the other hand, there is no solution for the resulting instance of

Â the independent set problem, then we know that the initial formula is unsatisfiable.

Â Indeed if it were satisfiable, if there were a satisfying assignment for

Â the initial formula, then this would give us an independent

Â set in the graph of size equal to the number of clauses.

Â Which would contradict to the fact that there is

Â no such independent set in the resulting graph.

Â