In these next three videos I want to highlight for you an unusual local search algorithm. It's unusual in that it's guarnetted to solve a non trivial and interesting problem in polynomial time. That problem is the two set problem which also furnishes an example of how local search can be applied. To constraint satisfaction problems. We've now mentioned 2-SAT in passing a number of times but let me just give you a very precise definition of the computational problem here. The input is a set of invariables x1 through xn at a set of m-closets. Each of variables is boolean. That is, you're allowed to set it to either true or to false. Each of the m-closets is a disjunction that is a Or of 2 literals. Literals is simply either a variable or indication of that variable. Here is an example to make this clear. The example has 4 variables and 4 clauses. The variables are X1 through X4. So, the first clause is X1 or X2. So, its standard use is V symbol to denote logical OR. So, what this clause means is that its satisfied if either X1 is true or if X2 is true. The only way you can screw up satisfying this clause is by setting both X1 and and X2 to false. The next clause has the form not-X1 or X3. The only way you can screw up satisfying this clause is by setting X1 to be true and X3 to be false. Then we're going to have a clause x3 or x4. Again this is satisfied unless you wind up setting x3 and x4 both to be false. And then finally we have a clause not x2 or not x4. And this is satisfied except in the case that you assign both x2 and x4 to be true. Because we're interested in whether all of the clauses can be simultaneously satisfied, one often joins the clauses using logical and symbols. That's what this upside down V denotes. So that's would a 2-SAT instance looks like and then we're just interested in a decision problem given such an instance, we just want to know Is it or Is it not possible to assign values to the invariables, True or False. So that every single one of the M clauses is satisfied. The two set instance that I gave you as an example is indeed satisfiable. There's actually more than 1 satisfying assignment but here's a way to produce one of them. Let's start with the first clause, to satisfy either X1 or X2 it needs to be set. to true. Let's go ahead and set x1 to be true. That takes care of the first clause. Now we look at the second clause and we notice, oops, if we set x1 to be true the only way we can satisfy the second clause is by setting x3 to be true. Let's do that. X1 and x3 are true. X2 and x4 we haven't assigned. Now, by assigning X3 to be true we knock off not just that 2nd clause, we also satisfy the 3rd clause. So that leaves us with the 4th clause, and now we just got to make sure we set either X2 or X4 to be false. Let's just go ahead and set them both to be false. That satisfies all of the clauses. Much is known where the competition tractability, or as the case may be intractability of contraints satisfaction problems. 2-SAT is not exceptional in that sense we know all kinds of things about it. It is, it is exceptional in that it is polynomial time [UNKNOWN]. There are many ways of proving this fact. Alumni of part one may already be familiar with one really nice way, which to reduce the 2-SAT problem to computing of the strongly connected components of a suitable directed graph. That reduction in fact shows that the 2-SAT problem can be solved in linear Time. Another way you can establish its computational tractability is using a type of backtracking algorithm. And by backtracking here I mean something sort of similar to what we did when we gave our faster exponential time algorithm for the vertex cover problem, for instances which have small vertex cover, small optimal solution. Both of these proofs of computational tractability are non-trivial. I'm not going to discuss the mirror because instead I want to spend our time on a local search algorithm. Roughly speaking, the way the back-tracking algorithm works in a 2 set instance is you start by looking at some variable, let's say variable X1. And, as a tentative working hypothesis, you assign x1 the value of, true. Now, through the clauses, setting x1 to be true, has ramifications for what other variables, have to necessarily be, if you're going to have a satisfying assignment. So you go ahead and propogate those implications, to the rest of the The variables. If you reach a contradiction, if there's one clause demanding that x7 is set to true and a different clause demanding that x7 is set to false. You know that it didn't work out. X1 is not going to be true in any satisfying assignment. So you back track and you try again, setting it to be false. And seeing if that works out. If on the other hand you're able to consistently propagate all of these implications from X1 being equal to true to other variables, then you can just try to extend that satisfying assignment by walking up to a different variable and setting that tentatively to be, say, true. It's possible to organize this search so that you can correctly determine whether or not a 2-SAT instance has the satisfying assignment in polynomial time. Again, a non-trivial exercise. If you're interested, think through the Details. We're going to instead focus on a very cool, randomized local search algorithm, that again, solves 2 side instances in polynomial time. I don't want to give you the wrong idea, as we discussed earlier, generally local search heuristics are not guaranteed to run in polynomial time. As we said, that's true even in the weighted version of the maximum cut problem. This 2-SAT example is the rare case where we can prove it's guaranteed to converge with a correct answer quickly. You can use local search not merely to identify computationally tractable versions of satisfiability, but also to improve over naive brute force search for NP complete versions of satisfiability. In particular, let's talk about the 3-sat problem. So 3-sat, no surprise, is the same as 2-SAT, except the clauses involve three literals rather than two. So while a clause in a 2-SAT instance can be thought of as forbidding one of the four possible joint assignments of a pair of variables, a clause in a 3-sat instance can be thought of as forbidding one of the eight possible joint values for a triple variable. Bumping up the clause length from 2 or 3 changes the problem from computationally tractable to computationally intractable. Indeed 3-SAT is in some sense the canonical NP-complete problem. You'll often see the Cook Levin theorem stated as 3-SAT NP-complete. But just because this MP complete doesn't automatically mean, we take them with any interesting algorithms.So Brude-force search would just try every possible assignment to the variables, that's going to take time roughly 2 2^n. Remarkably randomized local search lets you improve dramatically over the running time of naive brute force search. Rather than a running time of roughly 2^n a very clever twist on the 2-SAT algorithm that we're about to discuss, which was in polynomial time. A twist on that for 3-SAT runs in time roughly 4/3. Raised to the N, way better than 2^N. This is a relatively recent result, only about a decade old due to Schoning. I want to focus here on how to use randomized local search to solve 2-SAT and polynomial time. The improvement over brute force search for 3-SAT will have to wait until another. Another day. This algorithm is due to Papi Dimitru from a little over 20 years ago, and the very elegant pseudocode is as follows. So the algorithm has 2 loops, but the outer loop's responsibility is just to run the budget independent random trials. For those of you who are an alumni of part 1, let me make an analogy with Cargill's randomized contraction algorithm. So for that minimum cut algorithm, we had our basic randomized algorithm And then we ran it a bunch of times, a bunch of independent trials, hoping that 1 of the independent trials would find us the minimum cut. Same things going to be going on here, the meat of the algorithm is in the inner loop. That has some probability of finding a satisfying assignment and then we just run that basic subroutine a bunch of times, hoping that 1 of the trials will find us a satisfying assignment. So conceptually you should just focus on a fixed iteration of this outer 4 loop. They're all exactly the same, they just use different sets of random coins. In a given iteration of this outer loop, we're just going to be doing straightforward local search. So we have to specify what's the space of solutions? Well those are just all of the ways of assigning the invariables to true and false, all possible assignments. We have to specify the neighboring solution. That's just going to be the one we discussed, so 2 assignments will be neighboring if they differ only in the flip of a value of a single variable. We have to make a decision about where we start the local search. We're going to do it in just the obvious randomized way, from a uniform and random assignment of the variables. After we've settled on a random initial assignment, we just do local search. That is, we just keep flipping variables, trying to improve the quality of the current assign Now one thing that's going to be a little bit different from this algorithm, relative to the generic local search algorithm we discussed in the previous video, is I'm going to place an a priori bound on how many local moves we're going to do before we give up. One obvious motivation for that is, if we want a polynomial time algorithm [INAUDIBLE] This will ensure that the algorithm will not run for too many steps. So the magic number, which we'll motivate when we analyze the algorithm, is 2n^2. That's how many variable flips we're going to make before we give up and return to the next independent trial. in the outer for loop. Remember n denotes the number of variables. In each iteration of the inner for loop we first check just to see if the current assignment is in fact satisfiable, if it satisfies all the clauses. If so, we're done, we halt and report that back. Suppose the current assignment is not satisfy. What does that mean? That means there's one clause or maybe many clauses which are not currently satisfied. SO, for example, maybe there's some clause involving the variables X3 and X7. And the we unfortunately set X3 to be true, and X7 to be false. And that's exactly the joint value forbidden by this clause. That is, maybe the clause is not x3 or x7. So what do we do next? Well next we do an iteration of local search. We try and improve our assignment. How do we do that? Well we pick an unsatisfied clause.If there are many such clauses, we pick one arbitrarily and we try to make amends with this clause by flipping the values with one of the variables in the clause. So, in our example we're either going to flip x3 from true to false. That would satisfy the clause. Or we're going to flip x7 from false to true. That would also satisfy the clause. Assuming the clause is not x3 or x7. Now either one of these variable flips would succeed in changing this clause from unsatisfied to satisfied, and you could think of various clever heuristics about which of the 2 variables you decide to flip, but we're going to take the simplest way forward. We're just going to pick Pick between the two 50-50 so again how do we modify the assignment which choose an arbitrary unsatisfied clause, we pick one or two variables in the clause uniformly or random and we flip the value of that variable. Now what makes this algorithm so frightening to think about and my best guess for the reason why this very elegant algorithm wasn't analysed before 1991, is that you can do some serious damage when you flip one of these variables. I mean, yeah, the var, the constraint you started with is going to go from unsatisfied to satisfied but for all you know all these other clauses are going to go from satisfied to unsatisfied. [INAUDIBLE] If, for example, you take the variable x3 and you flip it from true to false, well yeah, that's great for this clause. It was not x3 or 7. It becomes true, it becomes satisfied, but maybe there are a zillion other clause where x3 appears un-negated, it's x3 or something else and perhaps by switching x3 to go from true to false a bunch of those have now become unsatisfied. So in no way are you always increasing the number of satisfied clauses when you do an iteration of this local search. It's very non standard local search algorithm in that sense. To complete the description of this algorithm I have to tell you what happens if it never finds a satisfying assignment. Of course, if it does find such an assignment, it quits while it's ahead, it just returns that satisfying assignment. But if they're all after these 2N^2*LogN steps it's never found a satisfying assignment, it does something very arrogant. It just declares that well, if I didn't find a satisfying assignment, I think that one doesn't exist. Here is 2 obvious, positive statement we could make about this randomized local search algorithm for 2-SAT. First of all, it runs in polynomial time, and that's with probability 1, no matter how the coin flips or how the algorithms play out. That's because we explicitly control the number of iterations of local search. It's big o of n^2 log n, so even with the sloppiest implementation you could imagine of this algorithm, it's going to run. Run in polynomial time. Let's turn to the issue of correctness, and let's separate two side instances into those that are satisfiable, where there exists a satisfying assignment, and those that are unsatisfiable. The second obvious good property of this local search algorithm is that it's always going to be correct, if you feed into it in an unsatisfiable instance. Why? But what's the algorithm going to do on such an instance, well it's going to rummuage around amongst the possible assignments for these 2n square logN steps, trying out different ones, obviously none of them will be satisfying 'cause there are no satisfying assignments, and at the end a the day the algorithm will correctly conclude that the instance is in fact unsatisfiable. But the key question is, what happens on satisfiable instances. If there is somewhere out there in the exponentially big space of assignments one that satisfies all of the assignments, is this algorithm going to find one in its mere 2n'2*logN steps. Now I have to tweak that question a little bit. This is, after all, a randomized algorithm and there's some tiny probability that the coin flips could conspire to stymie the algorithm from finding a satisfying assignment. So, what I really mean is, could it be the case that with probability very close to one on every satisfiable 2-SAT instance. This simple randomized local search algorithms, actually going to come up with a satisfying assignment.