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.