# MAX-SAT

Suppose that we have a number of boolean variables ${\displaystyle x_{1},x_{2},\ldots ,\in \{\mathrm {true} ,\mathrm {false} \}}$. A literal is either a variable ${\displaystyle x_{i}}$ itself or its negation ${\displaystyle \neg x_{i}}$. A logic expression is a conjunctive normal form (CNF) if it is written as the conjunction(AND) of a set of clauses, where each clause is a disjunction(OR) of literals. For example:

${\displaystyle (x_{1}\vee \neg x_{2}\vee \neg x_{3})\wedge (\neg x_{1}\vee \neg x_{3})\wedge (x_{1}\vee x_{2}\vee x_{4})\wedge (x_{4}\vee \neg x_{3})\wedge (x_{4}\vee \neg x_{1}).}$

The satisfiability (SAT) problem is that given as input a CNF formula decide whether the CNF is satisfiable, i.e. there exists an assignment of variables to the values of true and false so that all clauses are true. SAT is the first problem known to be NP-complete (the Cook-Levin theorem).

We consider the the optimization version of SAT, which ask for an assignment that the number of satisfied clauses is maximized.

 Problem (MAX-SAT) Given a conjunctive normal form (CNF) formula of ${\displaystyle m}$ clauses defined on ${\displaystyle n}$ boolean variables ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$, find a truth assignment to the boolean variables that maximizes the number of satisfied clauses.

## The Probabilistic Method

A straightforward way to solve Max-SAT is to uniformly and independently assign each variable a random truth assignment. The following theorem is proved by the probabilistic method.

 Theorem For any set of ${\displaystyle m}$ clauses, there is a truth assignment that satisfies at least ${\displaystyle {\frac {m}{2}}}$ clauses.
Proof.
 For each variable, independently assign a random value in ${\displaystyle \{\mathrm {true} ,\mathrm {false} \}}$ with equal probability. For the ${\displaystyle i}$th clause, let ${\displaystyle X_{i}}$ be the random variable which indicates whether the ${\displaystyle i}$th clause is satisfied. Suppose that there are ${\displaystyle k}$ literals in the clause. The probability that the clause is satisfied is ${\displaystyle \Pr[X_{k}=1]\geq (1-2^{-k})\geq {\frac {1}{2}}}$. Let ${\displaystyle X=\sum _{i=1}^{m}X_{i}}$ be the number of satisfied clauses. By the linearity of expectation, ${\displaystyle \mathbf {E} [X]=\sum _{i=1}^{m}\mathbf {E} [X_{i}]\geq {\frac {m}{2}}.}$ Therefore, there exists an assignment such that at least ${\displaystyle {\frac {m}{2}}}$ clauses are satisfied.
${\displaystyle \square }$

Note that this gives a randomized algorithm which returns a truth assignment satisfying at least ${\displaystyle {\frac {m}{2}}}$ clauses in expectation. There are totally ${\displaystyle m}$ clauses, thus the optimal solution is at most ${\displaystyle m}$, which means that this simple randomized algorithm is a ${\displaystyle {\frac {1}{2}}}$-approximation algorithm for the MAX-CUT problem.

## LP Relaxation + Randomized Rounding

For a clause ${\displaystyle C_{j}}$, let ${\displaystyle C_{i}^{+}}$ be the set of indices of the variables that appear in the uncomplemented form in clause ${\displaystyle C_{j}}$, and let ${\displaystyle C_{i}^{-}}$ be the set of indices of the variables that appear in the complemented form in clause ${\displaystyle C_{j}}$. The Max-SAT problem can be formulated as the following integer linear programing.

{\displaystyle {\begin{aligned}{\mbox{maximize}}&\quad \sum _{j=1}^{m}z_{j}\\{\mbox{subject to}}&\quad \sum _{i\in C_{j}^{+}}y_{i}+\sum _{i\in C_{j}^{-}}(1-y_{i})\geq z_{j},&&\forall 1\leq j\leq m\\&\qquad \qquad y_{i}\in \{0,1\},&&\forall 1\leq i\leq n\\&\qquad \qquad z_{j}\in \{0,1\},&&\forall 1\leq j\leq m\end{aligned}}}

Each ${\displaystyle y_{i}}$ in the programing indicates the truth assignment to the variable ${\displaystyle x_{i}}$, and each ${\displaystyle z_{j}}$ indicates whether the claus ${\displaystyle C_{j}}$ is satisfied. The inequalities ensure that a clause is deemed to be true only if at least one of the literals in the clause is assigned the value 1.

The integer linear programming is relaxed to the following linear programming:

{\displaystyle {\begin{aligned}{\mbox{maximize}}&\quad \sum _{j=1}^{m}z_{j}\\{\mbox{subject to}}&\quad \sum _{i\in C_{j}^{+}}y_{i}+\sum _{i\in C_{j}^{-}}(1-y_{i})\geq z_{j},&&\forall 1\leq j\leq m\\&\qquad \qquad 0\leq y_{i}\leq 1,&&\forall 1\leq i\leq n\\&\qquad \qquad 0\leq z_{j}\leq 1,&&\forall 1\leq j\leq m\end{aligned}}}

Let ${\displaystyle y_{i}^{*}}$ and ${\displaystyle z_{j}^{*}}$ be the fractional optimal solutions to the above linear programming. Clearly, ${\displaystyle \sum _{j=1}^{m}z_{j}^{*}}$ is an upper bound on the optimal number of satisfied clauses, i.e. we have

${\displaystyle \mathrm {OPT} \leq \sum _{j=1}^{m}z_{j}^{*}}$.

Apply a very natural randomized rounding scheme. For each ${\displaystyle 1\leq i\leq n}$, independently

${\displaystyle y_{i}={\begin{cases}1&{\mbox{with probability }}y_{i}^{*}.\\0&{\mbox{with probability }}1-y_{i}^{*}.\end{cases}}}$

Correspondingly, each ${\displaystyle x_{i}}$ is assigned to TRUE independently with probability ${\displaystyle y_{i}^{*}}$.

 Lemma Let ${\displaystyle C_{j}}$ be a clause with ${\displaystyle k}$ literals. The probability that it is satisfied by randomized rounding is at least ${\displaystyle (1-(1-1/k)^{k})z_{j}^{*}}$.
Proof.
 Without loss of generality, we assume that all ${\displaystyle k}$ variables appear in ${\displaystyle C_{j}}$ in the uncomplemented form, and we assume that ${\displaystyle C_{j}=x_{1}\vee x_{2}\vee \cdots \vee x_{k}}$. The complemented cases are symmetric. Clause ${\displaystyle C_{j}}$ remains unsatisfied by randomized rounding only if every one of ${\displaystyle x_{i}}$, ${\displaystyle 1\leq i\leq k}$, is assigned to FALSE, which corresponds to that every one of ${\displaystyle y_{i}}$, ${\displaystyle 1\leq i\leq k}$, is rounded to 0. This event occurs with probability ${\displaystyle \prod _{i=1}^{k}(1-y_{i}^{*})}$. Therefore, the clause ${\displaystyle C_{j}}$ is satisfied by the randomized rounding with probability ${\displaystyle 1-\prod _{i=1}^{k}(1-y_{i}^{*})}$. By the linear programming constraints, ${\displaystyle y_{1}^{*}+y_{2}^{*}+\cdots +y_{k}^{*}\geq z_{j}^{*}}$. Then the value of ${\displaystyle 1-\prod _{i=1}^{k}(1-y_{i}^{*})}$ is minimized when all ${\displaystyle y_{i}^{*}}$ are equal and ${\displaystyle y_{i}^{*}={\frac {z_{j}^{*}}{k}}}$. Thus, the probability that ${\displaystyle C_{j}}$ is satisfied is ${\displaystyle 1-\prod _{i=1}^{k}(1-y_{i}^{*})\geq 1-(1-z_{j}^{*}/k)^{k}\geq (1-(1-1/k)^{k})z_{j}^{*}}$, where the last inequality is due to the concaveness of the function ${\displaystyle 1-(1-z_{j}^{*}/k)^{k}}$ of variable ${\displaystyle z_{j}^{*}}$.
${\displaystyle \square }$

For any ${\displaystyle k\geq 1}$, it holds that ${\displaystyle 1-(1-1/k)^{k}>1-1/e}$. Therefore, by the linearity of expectation, the expected number of satisfied clauses by the randomized rounding, is at least

${\displaystyle (1-1/e)\sum _{j=1}z_{j}^{*}\geq (1-1/e)\cdot \mathrm {OPT} }$.

The inequality is due to the fact that ${\displaystyle {\hat {z}}_{j}}$ are the optimal fractional solutions to the relaxed LP, thus are no worse than the optimal integral solutions.

## Choose a better solution

For any instance of the Max-SAT, let ${\displaystyle m_{1}}$ be the expected number of satisfied clauses when each variable is independently set to TRUE with probability ${\displaystyle {\frac {1}{2}}}$; and let ${\displaystyle m_{2}}$ be the expected number of satisfied clauses when we use the linear programming followed by randomized rounding.

We will show that on any instance of the Max-SAT, one of the two algorithms is a ${\displaystyle {\frac {3}{4}}}$-approximation algorithm.

 Theorem ${\displaystyle \max\{m_{1},m_{2}\}\geq {\frac {3}{4}}\cdot \mathrm {OPT} .}$
Proof.
 It suffices to show that ${\displaystyle {\frac {(m_{1}+m_{2})}{2}}\geq {\frac {3}{4}}\sum _{j=1}^{m}z_{j}^{*}}$. Letting ${\displaystyle S_{k}}$ denote the set of clauses that contain ${\displaystyle k}$ literals, we know that ${\displaystyle m_{1}=\sum _{k=1}^{n}\sum _{C_{j}\in S_{k}}(1-2^{-k})\geq \sum _{k=1}^{n}\sum _{C_{j}\in S_{k}}(1-2^{-k})z_{j}^{*}.}$ By the analysis of randomized rounding, ${\displaystyle m_{2}\geq \sum _{k=1}^{n}\sum _{C_{j}\in S_{k}}(1-(1-1/k)^{k})z_{j}^{*}.}$ Thus ${\displaystyle {\frac {(m_{1}+m_{2})}{2}}\geq \sum _{k=1}^{n}\sum _{C_{j}\in S_{k}}{\frac {1-2^{-k}+1-(1-1/k)^{k}}{2}}z_{j}^{*}.}$ An easy calculation shows that ${\displaystyle {\frac {1-2^{-k}+1-(1-1/k)^{k}}{2}}\geq {\frac {3}{4}}}$ for any ${\displaystyle k}$, so that we have ${\displaystyle {\frac {(m_{1}+m_{2})}{2}}\geq {\frac {3}{4}}\sum _{k=1}^{n}\sum _{C_{j}\in S_{k}}z_{j}^{*}={\frac {3}{4}}\sum _{j=1}^{m}z_{j}^{*}\geq {\frac {3}{4}}\cdot \mathrm {OPT} .}$
${\displaystyle \square }$

# Lovász Local Lemma

Consider a set of "bad" events ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$. Suppose that ${\displaystyle \Pr[A_{i}]\leq p}$ for all ${\displaystyle 1\leq i\leq n}$. We want to show that there is a situation that none of the bad events occurs. Due to the probabilistic method, we need to prove that

${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]>0.}$
Case 1: mutually independent events.

If all the bad events ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ are mutually independent, then

${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]\geq (1-p)^{n}>0,}$

for any ${\displaystyle p<1}$.

Case 2: arbitrarily dependent events.

On the other hand, if we put no assumption on the dependencies between the events, then by the union bound (which holds unconditionally),

${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]=1-\Pr \left[\bigvee _{i=1}^{n}A_{i}\right]\geq 1-np,}$

which is not an interesting bound for ${\displaystyle p\geq {\frac {1}{n}}}$. We cannot improve bound without further information regarding the dependencies between the events.

We would like to know what is going on between the two extreme cases: mutually independent events, and arbitrarily dependent events. The Lovász local lemma provides such a tool.

The local lemma is powerful tool for showing the possibility of rare event under limited dependencies. The structure of dependencies between a set of events is described by a dependency graph.

 Definition Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ be a set of events. A graph ${\displaystyle D=(V,E)}$ on the set of vertices ${\displaystyle V=\{1,2,\ldots ,n\}}$ is called a dependency graph for the events ${\displaystyle A_{1},\ldots ,A_{n}}$ if for each ${\displaystyle i}$, ${\displaystyle 1\leq i\leq n}$, the event ${\displaystyle A_{i}}$ is mutually independent of all the events ${\displaystyle \{A_{j}\mid (i,j)\not \in E\}}$.
Example
Let ${\displaystyle X_{1},X_{2},\ldots ,X_{m}}$ be a set of mutually independent random variables. Each event ${\displaystyle A_{i}}$ is a predicate defined on a number of variables among ${\displaystyle X_{1},X_{2},\ldots ,X_{m}}$. Let ${\displaystyle v(A_{i})}$ be the unique smallest set of variables which determine ${\displaystyle A_{i}}$. The dependency graph ${\displaystyle D=(V,E)}$ is defined by
${\displaystyle (i,j)\in E}$ iff ${\displaystyle v(A_{i})\cap v(A_{j})\neq \emptyset }$.

The following lemma, known as the Lovász local lemma, first proved by Erdős and Lovász in 1975, is an extremely powerful tool, as it supplies a way for dealing with rare events.

 Lovász Local Lemma (symmetric case) Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ be a set of events, and assume that the following hold: for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq p}$; the maximum degree of the dependency graph for the events ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ is ${\displaystyle d}$, and ${\displaystyle ep(d+1)\leq 1}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]>0}$.

## Non-constructive Poof of LLL

We will prove a general version of the local lemma, where the events ${\displaystyle A_{i}}$ are not symmetric. This generalization is due to Spencer.

 Lovász Local Lemma (general case) Let ${\displaystyle D=(V,E)}$ be the dependency graph of events ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$. Suppose there exist real numbers ${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$ such that ${\displaystyle 0\leq x_{i}<1}$ and for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq x_{i}\prod _{(i,j)\in E}(1-x_{j})}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]\geq \prod _{i=1}^{n}(1-x_{i})}$.
Proof.

We can use the following probability identity to compute the probability of the intersection of events:

 Lemma 1 ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]=\prod _{i=1}^{n}\Pr \left[{\overline {A_{i}}}\mid \bigwedge _{j=1}^{i-1}{\overline {A_{j}}}\right]}$.
Proof.
 By definition of conditional probability, ${\displaystyle \Pr \left[{\overline {A_{n}}}\mid \bigwedge _{i=1}^{n-1}{\overline {A_{i}}}\right]={\frac {\Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]}{\Pr \left[\bigwedge _{i=1}^{n-1}{\overline {A_{i}}}\right]}}}$, so we have ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]=\Pr \left[\bigwedge _{i=1}^{n-1}{\overline {A_{i}}}\right]\Pr \left[{\overline {A_{n}}}\mid \bigwedge _{i=1}^{n-1}{\overline {A_{i}}}\right]}$. The lemma is proved by recursively applying this equation.
${\displaystyle \square }$

Next we prove by induction on ${\displaystyle m}$ that for any set of ${\displaystyle m}$ events ${\displaystyle i_{1},\ldots ,i_{m}}$,

${\displaystyle \Pr \left[A_{i_{1}}\mid \bigwedge _{j=2}^{m}{\overline {A_{i_{j}}}}\right]\leq x_{i_{1}}}$.

The local lemma is a direct consequence of this by applying Lemma 1.

For ${\displaystyle m=1}$, this is obvious. For general ${\displaystyle m}$, let ${\displaystyle i_{2},\ldots ,i_{k}}$ be the set of vertices adjacent to ${\displaystyle i_{1}}$ in the dependency graph. Clearly ${\displaystyle k-1\leq d}$. And it holds that

${\displaystyle \Pr \left[A_{i_{1}}\mid \bigwedge _{j=2}^{m}{\overline {A_{i_{j}}}}\right]={\frac {\Pr \left[A_{i}\wedge \bigwedge _{j=2}^{k}{\overline {A_{i_{j}}}}\mid \bigwedge _{j=k+1}^{m}{\overline {A_{i_{j}}}}\right]}{\Pr \left[\bigwedge _{j=2}^{k}{\overline {A_{i_{j}}}}\mid \bigwedge _{j=k+1}^{m}{\overline {A_{i_{j}}}}\right]}}}$,

which is due to the basic conditional probability identity

${\displaystyle \Pr[A\mid BC]={\frac {\Pr[AB\mid C]}{\Pr[B\mid C]}}}$.

We bound the numerator

{\displaystyle {\begin{aligned}\Pr \left[A_{i_{1}}\wedge \bigwedge _{j=2}^{k}{\overline {A_{i_{j}}}}\mid \bigwedge _{j=k+1}^{m}{\overline {A_{i_{j}}}}\right]&\leq \Pr \left[A_{i_{1}}\mid \bigwedge _{j=k+1}^{m}{\overline {A_{i_{j}}}}\right]\\&=\Pr[A_{i_{1}}]\\&\leq x_{i_{1}}\prod _{(i_{1},j)\in E}(1-x_{j}).\end{aligned}}}

The equation is due to the independence between ${\displaystyle A_{i_{1}}}$ and ${\displaystyle A_{i_{k}+1},\ldots ,A_{i_{m}}}$.

The denominator can be expanded using Lemma 1 as

${\displaystyle \Pr \left[\bigwedge _{j=2}^{k}{\overline {A_{i_{j}}}}\mid \bigwedge _{j=k+1}^{m}{\overline {A_{i_{j}}}}\right]=\prod _{j=2}^{k}\Pr \left[{\overline {A_{i_{j}}}}\mid \bigwedge _{\ell =j+1}^{m}{\overline {A_{i_{\ell }}}}\right]}$

which by the induction hypothesis, is at least

${\displaystyle \prod _{j=2}^{k}(1-x_{i_{j}})=\prod _{\{i_{1},i_{j}\}\in E}(1-x_{j})}$

where ${\displaystyle E}$ is the edge set of the dependency graph.

Therefore,

${\displaystyle \Pr \left[A_{i_{1}}\mid \bigwedge _{j=2}^{m}{\overline {A_{i_{j}}}}\right]\leq {\frac {x_{i_{1}}\prod _{(i_{1},j)\in E}(1-x_{j})}{\prod _{\{i_{1},i_{j}\}\in E}(1-x_{j})}}\leq x_{i_{1}}.}$

Applying Lemma 1,

{\displaystyle {\begin{aligned}\Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]&=\prod _{i=1}^{n}\Pr \left[{\overline {A_{i}}}\mid \bigwedge _{j=1}^{i-1}{\overline {A_{j}}}\right]\\&=\prod _{i=1}^{n}\left(1-\Pr \left[A_{i}\mid \bigwedge _{j=1}^{i-1}{\overline {A_{j}}}\right]\right)\\&\geq \prod _{i=1}^{n}\left(1-x_{i}\right).\end{aligned}}}
${\displaystyle \square }$

To prove the symmetric case. Let ${\displaystyle x_{i}={\frac {1}{d+1}}}$ for all ${\displaystyle i=1,2,\ldots ,n}$. Note that ${\displaystyle \left(1-{\frac {1}{d+1}}\right)^{d}>{\frac {1}{\mathrm {e} }}}$.

If the following conditions are satisfied:

1. for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq p}$;
2. ${\displaystyle ep(d+1)\leq 1}$;

then for all ${\displaystyle 1\leq i\leq n}$,

${\displaystyle \Pr[A_{i}]\leq p\leq {\frac {1}{e(d+1)}}<{\frac {1}{d+1}}\left(1-{\frac {1}{d+1}}\right)^{d}\leq x_{i}\prod _{(i,j)\in E}(1-x_{j})}$.

Due to the local lemma for general cases, this implies that

${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]\geq \prod _{i=1}^{n}(1-x_{i})=\left(1-{\frac {1}{d+1}}\right)^{n}>0}$.

This gives the symmetric version of local lemma.

## Constructive Proof of LLL

We consider a restrictive case.

Let ${\displaystyle X_{1},X_{2},\ldots ,X_{m}\in \{\mathrm {true} ,\mathrm {false} \}}$ be a set of mutually independent random variables which assume boolean values. Each event ${\displaystyle A_{i}}$ is an AND of at most ${\displaystyle k}$ literals (${\displaystyle X_{i}}$ or ${\displaystyle \neg X_{i}}$). Let ${\displaystyle v(A_{i})}$ be the set of the ${\displaystyle k}$ variables that ${\displaystyle A_{i}}$ depends on. The probability that none of the bad events occurs is

${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right].}$

In this particular model, the dependency graph ${\displaystyle D=(V,E)}$ is defined as that ${\displaystyle (i,j)\in E}$ iff ${\displaystyle v(A_{i})\cap v(A_{j})\neq \emptyset }$.

Observe that ${\displaystyle {\overline {A_{i}}}}$ is a clause (OR of literals). Thus, ${\displaystyle \bigwedge _{i=1}^{n}{\overline {A_{i}}}}$ is a ${\displaystyle k}$-CNF, the CNF that each clause depends on ${\displaystyle k}$ variables. The probability

${\displaystyle \bigwedge _{i=1}^{n}{\overline {A_{i}}}>0}$

means that the the ${\displaystyle k}$-CNF ${\displaystyle \bigwedge _{i=1}^{n}{\overline {A_{i}}}}$ is satisfiable.

The satisfiability of ${\displaystyle k}$-CNF is a hard problem. In particular, 3SAT (the satisfiability of 3-CNF) is the first NP-complete problem (the Cook-Levin theorem). Given the current suspect on NP vs P, we do not expect to solve this problem generally.

However, the condition of the Lovasz local lemma has an extra assumption on the degree of dependency graph. In our model, this means that each clause shares variables with at most ${\displaystyle d}$ other clauses. We call a ${\displaystyle k}$-CNF with this property a ${\displaystyle k}$-CNF with bounded degree ${\displaystyle d}$.

Therefore, proving the Lovasz local lemma on the restricted forms of events as described above, can be reduced to the following problem:

Problem
Find a condition on ${\displaystyle k}$ and ${\displaystyle d}$, such that any ${\displaystyle k}$-CNF with bounded degree ${\displaystyle d}$ is satisfiable.

In 2009, Moser comes up with the following procedure solving the problem. He later generalizes the procedure to general forms of events. This not only gives a beautiful constructive proof to the Lovasz local lemma, but also provides an efficient randomized algorithm for finding a satisfiable assignment for a number of events with bounded dependencies.

Let ${\displaystyle \phi }$ be a ${\displaystyle k}$-CNF of ${\displaystyle n}$ clauses with bounded degree ${\displaystyle d}$, defined on variables ${\displaystyle X_{1},\ldots ,X_{m}}$. The following procedure find a satisfiable assignment for ${\displaystyle \phi }$.

 Solve(${\displaystyle \phi }$) Pick a random assignment of ${\displaystyle X_{1},\ldots ,X_{m}}$. While there is an unsatisfied clause ${\displaystyle C}$ in ${\displaystyle \phi }$ Fix(${\displaystyle C}$).

The sub-routine Fix is defined as follows:

 Fix(${\displaystyle C}$) Replace the variables in ${\displaystyle v(C)}$ with new random values. While there is unsatisfied clause ${\displaystyle D}$ that ${\displaystyle v(C)\cap v(D)\neq \emptyset }$ Fix(${\displaystyle D}$).

The procedure looks very simple. It just recursively fixes the unsatisfied clauses by randomly replacing the assignment to the variables.

We then prove it works.

#### Number of top-level callings of Fix

In Solve(${\displaystyle \phi }$), the subroutine Fix(${\displaystyle C}$) is called. We now upper bound the number of times it is called (not including the recursive calls).

Assume Fix(${\displaystyle C}$) always terminates.

Observation
Every clause that was satisfied before Fix(${\displaystyle C}$) was called will still remain satisfied and ${\displaystyle C}$ will also be satisfied after Fix(${\displaystyle C}$) returns.

The observation can be proved by induction on the structure of recursion. Since there are ${\displaystyle n}$ clauses, Solve(${\displaystyle \phi }$) makes at most ${\displaystyle n}$ calls to Fix.

We then prove that Fix(${\displaystyle C}$) terminates.

#### Termination of Fix

The idea of the proof is to reconstruct a random string.

Suppose that during the running of Solve(${\displaystyle \phi }$), the Fix subroutine is called for ${\displaystyle t}$ times (including all the recursive calls).

Let ${\displaystyle s}$ be the sequence of the random bits used by Solve(${\displaystyle \phi }$). It is easy to see that the length of ${\displaystyle s}$ is ${\displaystyle |s|=m+tk}$, because the initial random assignment of ${\displaystyle m}$ variables takes ${\displaystyle m}$ bits, and each time of calling Fix takes ${\displaystyle k}$ bits.

We then reconstruct ${\displaystyle s}$ in an alternative way.

Recall that Solve(${\displaystyle \phi }$) calls Fix(${\displaystyle C}$) at top-level for at most ${\displaystyle n}$ times. Each calling of Fix(${\displaystyle C}$) defines a recursion tree, rooted at clause ${\displaystyle C}$, and each node corresponds to a clause (not necessarily distinct, since a clause might be fixed for several times). Therefore, the entire running history of Solve(${\displaystyle \phi }$) can be described by at most ${\displaystyle n}$ recursion trees.

Observation 1
Fix a ${\displaystyle \phi }$. The ${\displaystyle n}$ recursion trees which capture the total running history of Solve(${\displaystyle \phi }$) can be encoded in ${\displaystyle n\log n+t(\log d+O(1))}$ bits.

Each root node corresponds to a clause. There are ${\displaystyle n}$ clauses in ${\displaystyle \phi }$. The ${\displaystyle n}$ root nodes can be represented in ${\displaystyle n\log n}$ bits.

The smart part is how to encode the branches of the tree. Note that Fix(${\displaystyle C}$) will call Fix(${\displaystyle D}$) only for the ${\displaystyle D}$ that shares variables with ${\displaystyle C}$. For a k-CNF with bounded degree ${\displaystyle d}$, each clause ${\displaystyle C}$ can share variables with at most ${\displaystyle d}$ many other clauses. Thus, each branch in the recursion tree can be represented in ${\displaystyle \log d}$ bits. There are extra ${\displaystyle O(1)}$ bits needed to denote whether the recursion ends. So totally ${\displaystyle n\log n+t(\log d+O(1))}$ bits are sufficient to encode all ${\displaystyle n}$ recursion trees.

Observation 2
The random sequence ${\displaystyle s}$ can be encoded in ${\displaystyle m+n\log n+t(\log d+O(1))}$ bits.

With ${\displaystyle n\log n+t(\log d+O(1))}$ bits, the structure of all the recursion trees can be encoded. With extra ${\displaystyle m}$ bits, the final assignment of the ${\displaystyle m}$ variables is stored.

We then observe that with these information, the sequence of the random bits ${\displaystyle s}$ can be reconstructed from backwards from the final assignment.

The key step is that a clause ${\displaystyle C}$ is only fixed when it is unsatisfied (obvious), and an unsatisfied clause ${\displaystyle C}$ must have exact one assignment (a clause is OR of literals, thus has exact one unsatisfied assignment). Thus, each node in the recursion tree tells the ${\displaystyle k}$ random bits in the random sequence ${\displaystyle s}$ used in the call of the Fix corresponding to the node. Therefore, ${\displaystyle s}$ can be reconstructed from the final assignment plus at most ${\displaystyle n}$ recursion trees, which can be encoded in at most ${\displaystyle m+n\log n+t(\log d+O(1))}$ bits.

The following theorem lies in the heart of the Kolmogorov complexity. The theorem states that random sequence is incompressible.

 Theorem (Kolmogorov) For any encoding scheme , with high probability, a random sequence ${\displaystyle s}$ is encoded in at least ${\displaystyle |s|}$ bits.

Applying the theorem, we have that with high probability,

${\displaystyle m+n\log n+t(\log d+O(1))\geq |s|=m+tk}$.

Therefore,

${\displaystyle t(k-O(1)-\log d)\leq n\log n.}$

In order to bound ${\displaystyle t}$, we need

${\displaystyle k-O(1)-\log d>0}$,

which hold for ${\displaystyle d<2^{k-\alpha }}$ for some constant ${\displaystyle \alpha >0}$. In fact, in this case, ${\displaystyle t=O(n\log n)}$, the running time of the procedure is bounded by a polynomial!

#### Back to the local lemma

We showed that for ${\displaystyle d<2^{k-O(1)}}$, any ${\displaystyle k}$-CNF with bounded degree ${\displaystyle d}$ is satisfiable, and the satisfied assignment can be found within polynomial time with high probability. Now we interprete this in a language of the local lemma.

Recall that the symmetric version of the local lemma:

 Theorem (The local lemma: symmetric case) Let ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ be a set of events, and assume that the following hold: for all ${\displaystyle 1\leq i\leq n}$, ${\displaystyle \Pr[A_{i}]\leq p}$; the maximum degree of the dependency graph for the events ${\displaystyle A_{1},A_{2},\ldots ,A_{n}}$ is ${\displaystyle d}$, and ${\displaystyle ep(d+1)\leq 1}$. Then ${\displaystyle \Pr \left[\bigwedge _{i=1}^{n}{\overline {A_{i}}}\right]>0}$.

Suppose the underlying probability space is a number of mutually independent uniform random boolean variables, and the evens ${\displaystyle {\overline {A_{i}}}}$ are clauses defined on ${\displaystyle k}$ variables. Then,

${\displaystyle p=2^{-k}}$

thus, the condition ${\displaystyle ep(d+1)\leq 1}$ means that

${\displaystyle d<2^{k}/e}$

which means the Moser's procedure is asymptotically optimal on the degree of dependency.