0:00

The next technique that we are going to consider is called local search.

Â This is also widely used in practise technique.

Â It is used both for search problems and for optimization problems.

Â It's main idea is roughly the following.

Â You start with some initial solution, then you iteratively do the following.

Â If your current solution is not good enough,

Â you try to change it little bit somewhere to get a new solution which is,

Â in some sense, better, or which fixes something.

Â So pictorially it looks as follows, you go from one solution to a solution which

Â is close to it, which results from the current solution by some small change.

Â Then to some other solution, then to some other,

Â until you get a solution which is good enough for you.

Â So this is a very very vague explanation of this technique.

Â We will now give a more concrete explanation of the local search algorithm.

Â So this is how a local search algorithm might look like for

Â the three variability problem.

Â Consider a formula in 3-CNF and denote, it's variables by x1, x2 and so on xn.

Â So it has n Boolean variables.

Â So a candidate solution for such a formula is just a truth assignment for

Â all these variables.

Â So in other words, this is just a vector in {0, 1} to the n, right?

Â Since we are going to apply local search, that is, we need to change each

Â candidate solution a little bit, to go to another solution in its neighborhood.

Â We need to define the notion of distance between two different candidate solutions.

Â So let alpha and beta be two such candidate solutions, that is vectors in 0,

Â 1 to the n.

Â We define the distance between them as the number of bits where they differ.

Â So, more formally the distance we just, we just called distance.

Â The distance between alpha and

Â beta is a number of such indices i where alphai is not equal to betai.

Â 2:28

And this Boolean assignment, we center this Boolean assignment and write your 0.

Â So this is alpha, this is R contains just exactly the same Boolean assignment.

Â The hamming ball was radius one and

Â center at the same Boolean assignment contains five different assignments.

Â So in this case, by the way, n is equal to 4.

Â So first of all, it contains the center of this ball.

Â It also contains four Boolean assignments that resolved from

Â our initial assignment by changing just one beat.

Â Waits on.

Â The first one we change the first bit here.

Â We change the second bit here.

Â We change the third bit here.

Â We change the fourth bit.

Â Finally, the Hayman ball with the same center and

Â with radius 2 contains the following assignment.

Â So this is an assignment at distance one.

Â These are four assignments at distance one.

Â 3:32

I'm sorry, so this is an assignment at distance zero.

Â These are four assignments at distance one.

Â And this six assignments at distance exactly two.

Â This is a crucial Lemma for

Â our loca search algorithm, which checks satisfiability of a given formula.

Â Assume that we are given a formula F.

Â And together with this formula F we are given a Hamming ball.

Â We use center alpha and radius r for

Â which we know that is contains a satisfying assignment of a formula F.

Â Then we can find a satisfying assignment in this

Â ball in times 3r times the length of the formula.

Â This final assignment that we are going to find might coincide with be or

Â might be a different one.

Â But in any case,

Â if we know that this cannon ball contains a satisfying assignment,

Â then we will find some satisfying assignment in this running time.

Â This is how to do this.

Â We first check whether the assignment alpha,

Â namely the center of our current ball, satisfies the formula F.

Â 5:09

Let's then do the following.

Â Let's consider three different assignments: alpha i, alpha j,

Â and alpha k.

Â Alpha i differs from alpha only in the i speed.

Â Alpha j differs from alpha only in the j speed.

Â Finally, alpha k results from alpha by flipping the k speed.

Â What we know about these three assignments is that at least one of

Â them is closer to beta, right?

Â So we don't know which one, but we know for

Â sure that at least one of them is closer to beta then alpha, why is that?

Â Because beta satisfies the currently considerate clause.

Â So in beta, either x i is equal to 1, or x j is equal to 0, or x k is equal to 1.

Â So in at least Alpha I, or Alpha J, or Alpha K, we fix at the right bit.

Â The ones that have the same value in Beta.

Â So at least one of them is closer to Beta.

Â Probably two of them, or probably three of them, but it doesn't matter at this point.

Â What is important is that at least one of them is closer.

Â So we start with Alpha and then we consider three different assignments.

Â Alpha i, alpha j, alpha k.

Â For each of them we make the same step.

Â For each of them we also consider three different assignments.

Â And we always know that, at least in one of the branches we get closer to beta.

Â Since we know that the distance between alpha and

Â beta is at most r, just because beta lies in the hamming ball.

Â We center alpha we conclude that in the corresponding algorithms,

Â there are at most 3 to the r recursive calls.

Â 7:04

We know that somewhere in this ball, there is a satisfying assignment beta.

Â We don't know which one.

Â Of course we're only looking for a satisfying assignment but

Â I assume that there is a satisfying assignment, beta in this case.

Â Then at each step we do the following.

Â We select an unsatisfied clause and from alpha we move to one of, we try

Â all these three satisfying assignments that differ from alpha in just one bit.

Â We don't know in which direction we need to go but

Â we know that in at least one of these directions we get closer to beta.

Â Then for all these three assignments we repeat this procedure and in turn for

Â all of them we again repeat this procedure.

Â So eventually, if we make r steps, we will find an assignment beta, or

Â we will stop before this if we find another satisfying assignment.

Â The crucial observation is that to eventually find beta,

Â we need at most three to the r recursive calls.

Â This is just because the distance between alpha and beta is at most r, and

Â at each iteration in at least one of these three branches we get closer to beta.

Â This is of the resulting algorithm.

Â It is given a formula F, also an assignment alpha.

Â And in r.

Â And then it checks whether it tries to find a satisfying assignment in

Â a ball with center alpha and radius r.

Â We first check whether alpha satisfies the formula F.

Â If it does, we return alpha immediately.

Â Then we check whether the is equal to zero.

Â If it is equal to zero we return that ball.

Â Ball does not contain a satisfying assignment.

Â So we return not found.

Â So recall that if r is equal to zero then the responding ball contains

Â the assignment alpha itself.

Â Then we take any unsatisfied clause and we denote by xi, xj, and xk,

Â the variables from this clause.

Â Then we construct three different satisfying assignments.

Â Alpha i, alpha j, or alpha k.

Â 9:19

More precisely we first make the first recursive call.

Â We with parameters F, alpha i and r minus 1.

Â If it finds a satisfying assignment we immediately return.

Â If not, we make a second recursive call for F, alpha j and r minus one.

Â If it finds a satisfying assignment, we return immediately.

Â If not, we make a short recursive call.

Â So if none of them find a satisfying assignment we return not found.], okay?

Â Now we need to show how to use this procedure

Â which checks whether a bowl containing a satisfying assignment

Â to check whether the given formula is satisfied.

Â Well, assume that our initial formula, our formula F, is satisfiable,

Â and the reason it's satisfying assignment beta Well, there is a simple observation.

Â Assume that there are more 1's than 0's in the assignment beta,

Â then I claim that it's distance from all 1's assignment is, at most, n over 2.

Â Well, this is clear.

Â If there are more ones than zeros.

Â Then the number of ones in this assignment is at least n over 2.

Â Which means that the distance to the all-1's assignment is at most n/2.

Â Otherwise, the distance of this assignment to the all zero assignment,

Â that is an assignment which assigns zeros to all the variables is also at most n/2.

Â This means that to check the satisfiability of the formula F,

Â it is enough to check whether any of two huge balls contain

Â a satisfying assignment.

Â Once again, if there is a satisfying assignment beta of a formula F, and

Â it is contain It is contained either in a ball of radius n/2 with

Â center in all-1's assignment or

Â in a ball with radius n/2 whose center is in all-0's assignment.

Â So if none of these recursive calls finds a satisfying assignment,

Â then the initial formula is unsatisfiable for sure.

Â The running time of this algorithm is O of the size of the formula times 3

Â to the n/2.

Â This is just because we will make two calls to check for

Â two balls of radius n/2 and

Â each of these calls takes time roughly 3 to the n/2.

Â So this is roughly 1.733 to the n so

Â this is still exponential, still not acceptable in practice.

Â However, know that the same time that this has exponentially faster than a brute

Â force search algorithm.

Â because a brute force search algorithm runs in time 2 to the n and

Â algorithm runs in time 1.733 to the n This is roughly 1.15 to the n.

Â So it is exponentially faster.

Â Already for n = 100, for example, our algorithm is roughly

Â 1 million times faster than the brute force algorithm.

Â So this algorithm works well in theory.

Â And local search heuristics and local search ideas but

Â slightly different form are also widely used in modern set holders.

Â