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.