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.