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. 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. 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. 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. The last example is also an unsatisfiable formula where we have two variables and it is not difficult to see that this is also unsatisfiable. Just because these four clauses actually forbid all four possible ways of assigning the values x and y. For example, if we try to assign the value 1 to x and the value 0 to y. 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. 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. 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, 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. 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. 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. 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.
