0:00

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.

Â