0:00

In this lesson, we will consider all of the reasons

Â that solve NP-complete problems in special cases.

Â The main message of this lesson is the following.

Â The fact that your problem is NP-complete does not exclude a possibility of a very

Â efficient algorithm that solves your problem in some special restrictive cases.

Â So once again, the fact that the problem is NP-complete means that it is difficult

Â to design an efficient algorithm that works for all possible cases.

Â But it might be the case that for

Â some special cases there exists a much more efficient algorithm.

Â 0:39

Our first example of such a problem is 2-satisfiability problem.

Â For this problem, we will see a surprising connection between boolean formulas

Â in 2-CNF and graphs.

Â Namely, we will apply the depth-first search algorithm to

Â solve a special case of the satisfiability problem just in linear time.

Â The input of the 2-satisfiability problem, which is also abbreviated as just 2-SAT,

Â is a set of clauses, each of which contains at most two literals.

Â Recall that the literal is a boolean variable or

Â a negation of a boolean variable.

Â And what we need to find is to check whether we can assign boolean

Â values to the variables of this formula to satisfy all these clauses.

Â So what we need to return is as I said a satisfying assignment or

Â we need to report that there is no such satisfying assignment.

Â Let me give you a few two examples.

Â So this is a formula in 2-CNF.

Â So all clauses contain at most two literals and

Â it can be satisfied with the following assignment.

Â 1:50

Let's check it.

Â If x = 0, y = 1 and z = 0, so that means of course,

Â the first clause is satisfied by the literal y which has value 1.

Â The second clause is satisfied by the negation of z, so

Â z has value 0, so negation of z has value 1.

Â And finally, the last clause is satisfied by the negation of x, okay?

Â This is another formula in 2-CNF and it is unsatisfiable.

Â To see this, know that we have to closest of links one here, so

Â this is the first such clause and it forces us to assign the value 0.

Â So z must be equal to 0 if we would like to satisfy this formula.

Â 2:31

Similarly we need to assign the value 0 to y because of the last clause, right?

Â Then what is left is these two clauses.

Â Y and z, the literals y and z are already falsified in these two clauses.

Â So essentially what is left in this clause is in the first clause we have x,

Â in the second clause, we have not x.

Â And of course,

Â it is not possible to suggest [INAUDIBLE] these clauses by assigning x.

Â Okay, so this formula is unsatisfiable.

Â 3:23

Then we get the following clause, so which one?

Â This one, which is unsatisfied.

Â And no matter how we assign two values for these two variables,

Â we always get an unsatisfied clause.

Â Consider two clause of our input formula.

Â Say it contains letters l1 and l2.

Â Basically what it says is that we should not assign similar

Â [INAUDIBLE] value 0 to both l1 and l2.

Â Because in this case, this clause will be clearly falsified.

Â In other words, if we assign the value 0 to l1, we must assign the value 1 to l2.

Â Because this is the only way to satisfy this clause when l1 is already equal

Â to zero and vice-versa.

Â If we assign the value zero to l2, we must assign the value 1 to l1.

Â So this is the kind of implication and in fact,

Â implication is a well-known binary operation.

Â It is defined by the following truth table.

Â So it is equal to 1 in all cases except for the following one.

Â When x is equal to 1 and y is equal to 0,

Â the implication from x to y is also equal to 0.

Â In all other cases it is equal to 1.

Â What it does with y is, it says the following,

Â that falsity implies everything.

Â It is shown here.

Â If x if false, then it implies both the truth and the falsity.

Â However, if x is true,

Â it only implies the truth.

Â The implication from x to y when x is equal to 1 is only

Â equal to 1 when y is equal to 1 too.

Â 5:11

This observation brings us to the following so-called implication graph.

Â It is defined as follows, given a 2-CNF formula,

Â for each variable of this formula, we introduced two vertices.

Â One labeled with this variable and one labeled with its negation.

Â Then for each two clause that contains two literals, say l1 and

Â l2, we introduce two directed edges.

Â The first one goes from the negation of l1 to l2 and

Â the second one goes from the negation of l2 to l1, okay?

Â And finally for each clause of length one, which contains just some literal l.

Â We introduce an edge, a directed edge again,

Â that goes from the negation of l to the l itself.

Â 5:59

Okay, so in a sense this graph contains all

Â implications that I imposed by our input formula.

Â To give an example, consider the following 2-CNF formula.

Â Consisting of three variables, x, y, z and four clauses of length two.

Â To construct each implication graph, we first introduce six vertices,

Â two vertices for eachiInput variable.

Â This gives us the following six vertices, x nought x, y nought y, and z nought z.

Â Then we start introduce edges.

Â The first clause gives us the following two edges, namely an edge from x to y,

Â 6:41

this edge and the next from nought y to nought x.

Â Once again, it corresponds to the following clause.

Â Let's understand once again why these two edges correspond to this clause.

Â Well, what essentially is this

Â clause says is, is that if not x = 0,

Â which means that x is equal to 1,

Â then y must be equal to 1.

Â This is essentially what is given to us by this implication, right?

Â It says that if x is 1, then this also must be 1 to satisfy this implication.

Â 7:27

The other edge says that if this edge,

Â if not y = 1, this actually means that y = 0,

Â then not x must be equal to 1.

Â And this is indeed true, if y = 0,

Â then this literal is falsified in this clause.

Â Which means that the only way to satisfy it is to set not x to be equal to 1,

Â right?

Â Then we can continue in the same manner.

Â For the second clause, we introduce the following two edges.

Â For the set clause, we introduce the following two edges.

Â And finally for the last clause, for

Â the first one, we introduce the following two edges.

Â Now we have an implication graph.

Â Now we can see that some specific assignment of boolean values to

Â the variables of this formula.

Â For example, when x is equal to 1, y is equal to 1 and z is equal to 1,

Â all the clauses are satisfied.

Â It can be easily seen just by observing that each

Â clause in our input formula contains a positive literal.

Â By saying positive I mean a variable with no negation.

Â So for example here, y satisfies this clause here, z satisfies this clause here,

Â x satisfies this clause and the last clause is satisfied by z and y.

Â Also we can see that each edge in this graph is also in a sense satisfied.

Â 8:58

Now let's consider and as our assignment, that actually falsifies the input formula.

Â If we assign the value 0 to x, y and

Â z, then the first three clauses are satisfied.

Â The first one is satisfied by x, the second one by not y,

Â the third one by not z, but in the last clause, both the literals are equal to 0.

Â Okay, and

Â we see also that the corresponding two edges in the graph are also falsified.

Â By saying falsified I mean that they are the beginning of this edge has value 1.

Â So z is equal to 0, so not z is equal to 1.

Â While the end of this edge is equal to 0, right?

Â So, one does does not imply 0.

Â So truth does not imply falsity.

Â And the same for this edge.

Â In this case, y = 0, so this vertex has value 1.

Â While the end of this edge has the value 0.

Â And this is exactly the situation when the implication is falsified,

Â when it says that the truth implies falsity.

Â 10:06

Now our goal then, given this graph,

Â our goal is to assign the values to all the variables.

Â So if our input formula, so that all the edges are satisfied.

Â And that's we discussed already.

Â An edge is satisfied if and only if, well,

Â it is easier to say what it means for an edge to be falsified.

Â An edge is falsified, when its beginning is labeled with 1 and

Â its end is labeled with 0.

Â So we need an assignment to all the variables of our

Â input formula such that no edge is falsified.

Â