


Here are four common flavours of this monotonicity strategy:






Rather than deal with the Lovász local lemma in full generality, I will follow Fortnow and work with a special case of this lemma involving the {k}-satisfiability problem (in conjunctive normal form). Here, one is given a set of boolean variables {x_1,\ldots,x_n} together with their negations {\neg x_1, \ldots, \neg x_n}; we refer to the {2n} variables and their negations collectively as literals. We fix an integer {k \geq 2}, and define a (length {k}) clause to be a disjunction of {k} literals, for instance

\displaystyle  x_3 \vee \neg x_5 \vee x_9

is a clause of length three, which is true unless {x_3} is false, {x_5} is true, and {x_9} is false. We define the support of a clause to be the set of variables that are involved in the clause, thus for instance {x_3 \vee \neg x_5 \vee x_9} has support {\{x_3,x_5,x_9\}}. To avoid degeneracy we assume that no clause uses a variable more than once (or equivalently, all supports have cardinality exactly {k}), thus for instance we do not consider {x_3 \vee x_3 \vee x_9} or {x_3 \vee \neg x_3 \vee x_9} to be clauses.

Note that the failure of a clause reveals complete information about all {k} of the boolean variables in the support; this will be an important fact later on.

The {k}-satisfiability problem is the following: given a set {S} of clauses of length {k} involving {n} boolean variables {x_1,\ldots,x_n}, is there a way to assign truth values to each of the {x_1,\ldots,x_n}, so that all of the clauses are simultaneously satisfied?

For general {S}, this problem is easy for {k=2} (essentially equivalent to the problem of {2}-colouring a graph), but NP-complete for {k \geq 3} (this is the famous Cook-Levin theorem). But the problem becomes simpler if one makes some more assumptions on the set {S} of clauses. For instance, if the clauses in {S} have disjoint supports, then they can be satisfied independently of each other, and so one easily has a positive answer to the satisfiability problem in this case. (Indeed, one only needs each clause in {S} to have one variable in its support that is disjoint from all the other supports in order to make this argument work.)

Now suppose that the clauses {S} are not completely disjoint, but have a limited amount of overlap; thus most clauses in {S} have disjoint supports, but not all. With too much overlap, of course, one expects satisfability to fail (e.g. if {S} is the set of all length {k} clauses). But with a sufficiently small amount of overlap, one still has satisfiability:

Theorem 1 (Lovász local lemma, special case) Suppose that {S} is a set of length {k} clauses, such that the support of each clause {s} in {S} intersects at most {2^{k-C}} supports of clauses in {S} (including {s} itself), where {C} is a sufficiently large absolute constant. Then the clauses in {S} are simultaneously satisfiable.

One of the reasons that this result is powerful is that the bounds here are uniform in the number {n} of variables. Apart from the loss of {C}, this result is sharp; consider for instance the set {S} of all {2^k} clauses with support {\{x_1,\ldots,x_k\}}, which is clearly unsatisfiable.

The standard proof of this theorem proceeds by assigning each of the {n} boolean variables {x_1,\ldots,x_n} a truth value {a_1,\ldots,a_n \in \{ \hbox{true}, \hbox{false} \}} independently at random (with each truth value occurring with an equal probability of {1/2}); then each of the clauses in {S} has a positive zero probability of holding (in fact, the probability is {1-2^{-k}}). Furthermore, if {E_s} denotes the event that a clause {s \in S} is satisfied, then the {E_s} are mostly independent of each other; indeed, each event {E_s} is independent of all but most {2^{k-C}} other events {E_{s'}}. Applying the Lovász local lemma, one concludes that the {E_s} simultaneously hold with positive probability (if {C} is a little bit larger than {\log_2 e}), and the claim follows.

The textbook proof of the Lovász local lemma is short but nonconstructive; in particular, it does not easily offer any quick way to compute an actual satisfying assignment for {x_1,\ldots,x_n}, only saying that such an assignment exists. Moser’s argument, by contrast, gives a simple and natural algorithm to locate such an assignment (and thus prove Theorem 1). (The constant {C} becomes {3} rather than {\log_2 e}, although the {\log_2 e} bound has since been recovered in a paper of Moser and Tardos.)

As with the usual proof, one begins by randomly assigning truth values {a_1,\ldots,a_n \in \{ \hbox{true}, \hbox{false} \}} to {x_1,\ldots,x_n}; call this random assignment {A = (a_1,\ldots,a_n)}. If {A} satisfied all the clauses in {S}, we would be done. However, it is likely that there will be some non-empty subset {T} of clauses in {S} which are not satisfied by {A}.

We would now like to modify {A} in such a manner to reduce the number {|T|} of violated clauses. If, for instance, we could always find a modification {A'} of {A} whose set {T'} of violated clauses was strictly smaller than {T} (assuming of course that {T} is non-empty), then we could iterate and be done (this is basically a mass decrement argument). One obvious way to try to achieve this is to pick a clause {s} in {T} that is violated by {A}, and modify the values of {A} on the support of {s} to create a modified set {A'} that satisfies {s}, which is easily accomplished; in fact, any non-trivial modification of {A} on the support will work here. In order to maximize the amount of entropy in the system (which is what one wants to do for an entropy compression argument), we will choose this modification of {A'} randomly; in particular, we will use {k} fresh random bits to replace the {k} bits of {A} in the support of {s}. (By doing so, there is a small probability ({2^{-k}}) that we in fact do not change {A} at all, but the argument is (very) slightly simpler if we do not bother to try to eliminate this case.)

If all the clauses had disjoint supports, then this strategy would work without difficulty. But when the supports are not disjoint, one has a problem: every time one modifies {A} to “fix” a clause {s} by modifying the variables on the support of {s}, one may cause other clauses {s'} whose supports overlap those of {s} to fail, thus potentially increasing the size of {T} by as much as {2^{k-C}-1}. One could then try fixing all the clauses which were broken by the first fix, but it appears that the number of clauses needed to repair could grow indefinitely with this procedure, and one might never terminate in a state in which all clauses are simultaneously satisfied.

The key observation of Moser, as alluded earlier, is that each failure of a clause {s} for an assignment {A} reveals {k} bits of information about {A}, namely that the exact values that {A} assigns to the support of {s}. The plan is then to use each failure of a clause as a part of a compression protocol that compresses {A} (plus some other data) losslessly into a smaller amount of space. A crucial point is that at each stage of the process, the clause one is trying to fix is almost always going to be one that overlapped the clause that one had just previously fixed. Thus the total number of possibilities for each clause, given the previous clauses, is basically {2^{k-C}}, which requires only {k-C} bits of storage, compared with the {k} bits of entropy that have been eliminated. This is what is going to force the algorithm to terminate in finite time (with positive probability).

Let’s make the details more precise. We will need the following objects:

  • A truth assignment {A} of {n} truth values {a_1,\ldots,a_n}, which is initially assigned randomly, but which will be modified as the algorithm progresses;
  • A long random string {R} of bits, from which we will make future random choices, with each random bit being removed from {R} as it is read.

We also need a recursive algorithm {Fix(s)}, which modifies the string {A} to satisfy a clause {s} in {S} (and, as a bonus, may also make {A} obey some other clauses in {S} that it did not previously satisfy). It is defined recursively:

  • Step 1. If {A} already satisfies {s}, do nothing (i.e. leave {A} unchanged).
  • Step 2. Otherwise, read off {k} random bits from {R} (thus shortening {R} by {k} bits), and use these to replace the {k} bits of {A} on the support of {s} in the obvious manner (ordering the support of {s} by some fixed ordering, and assigning the {j^{th}} bit from {R} to the {j^{th}} variable in the support for {1 \leq j \leq k}).
  • Step 3. Next, find all the clauses {s'} in {S} whose supports intersect {s}, and which {A} now violates; this is a collection of at most {2^{k-C}} clauses, possibly including {s} itself. Order these clauses {s'} in some arbitrary fashion, and then apply {Fix(s')} to each such clause in turn. (Thus the original algorithm {Fix(s)} is put “on hold” on some CPU stack while all the child processes {Fix(s')} are executed; once all of the child processes are complete, {Fix(s)} then terminates also.)

An easy induction shows that if {Fix(s)} terminates, then the resulting modification of {A} will satisfy {s}; and furthermore, any other clause {s'} in {S} which was already satisfied by {A} before {Fix(s)} was called, will continue to be satisfied by {A} after {Fix(s)} is called. Thus, {Fix(s)} can only serve to decrease the number of unsatisfied clauses {T} in {S}, and so one can fix all the clauses by calling {Fix(s)} once for each clause in {T} – provided that these algorithms all terminate.

Each time Step 2 of the Fix algorithm is called, the assignment {A} changes to a new assignment {A'}, and the random string {R} changes to a shorter string {R'}. Is this process reversible? Yes – provided that one knows what clause {s} was being fixed by this instance of the algorithm. Indeed, if {s, A', R'} are known, then {A} can be recovered by changing the assignment of {A'} on the support of {s} to the only set of choices that violates {s}, while {R} can be recovered from {R'} by appending to {R'} the bits of {A} on the support of {s}.

This type of reversibility does not seem very useful for an entropy compression argument, because while {R'} is shorter than {R} by {k} bits, it requires about {\log |S|} bits to store the clause {s}. So the map {A+R \mapsto A'+R'+s} is only a compression if {\log |S| < k}, which is not what is being assumed here (and in any case the satisfiability of {S} in the case {\log |S| < k} is trivial from the union bound).

The key trick is that while it does indeed take {\log |S|} bits to store any given clause {s}, there is an economy of scale: after many recursive applications of the fix algorithm, the marginal amount of bits needed to store {s} drops to merely {k-C+O(1)}, which is less than {k} if {C} is large enough, and which will therefore make the entropy compression argument work.

Let’s see why this is the case. Observe that the clauses {s} for which the above algorithm {Fix(s)} is called come in two categories. Firstly, there are those {s} which came from the original list {T} of failed clauses. Each of these will require {O(\log |S|)} bits to store – but there are only {|T|} of them. Since {|T| \leq |S|}, the net amount of storage space required for these clauses is {O(|S| \log |S|)} at most. Actually, one can just store the subset {T} of {S} using {|S|} bits (one for each element of {S}, to record whether it lies in {T} or not).

Of more interest is the other category of clauses {s}, in which {Fix(s)} is called recursively from some previously invoked call {Fix(s')} to the fix algorithm. But then {s} is one of the at most {2^{k-C}} clauses in {S} whose support intersects that of {s'}. Thus one can encode {s} using {s'} and a number between {1} and {2^{k-C}}, representing the position of {s} (with respect to some arbitrarily chosen fixed ordering of {S}) in the list of all clauses in {S} whose supports intersect that of {s'}. Let us call this number the index of the call {Fix(s)}.

Now imagine that while the Fix routine is called, a running log file (or history) {H} of the routine is kept, which records {s} each time one of the original {|T|} calls {Fix(s)} with {s \in T} is invoked, and also records the index of any other call {Fix(s)} made during the recursive procedure. Finally, we assume that this log file records a termination symbol whenever a {Fix} routine terminates. By performing a stack trace, one sees that whenever a Fix routine is called, the clause {s} that is being repaired by that routine can be deduced from an inspection of the log file {H} up to that point.

As a consequence, at any intermediate stage in the process of all these fix calls, the original state {A+R} of the assignment and the random string of bits can be deduced from the current state {A'+R'} of these objects, plus the history {H'} up to that point.

Now suppose for contradiction that {S} is not satisfiable; thus the stack of fix calls can never completely terminate. We trace through this stack for {M} steps, where {M} is some large number to be chosen later. After these steps, the random string {R} has shortened by an amount of {Mk}; if we set {R} to initially have length {Mk}, then the string is now completely empty, {R' = \emptyset}. On the other hand, the history {H'} has size at most {O(|S|) + M(k-C+O(1))}, since it takes {|S|} bits to store the initial clauses in {T}, {O(|S|)+O(M)} bits to record all the instances when Step 1 occurs, and every subsequent call to Fix generates a {k-C}-bit number, plus possibly a termination symbol of size {O(1)}. Thus we have a lossless compression algorithm {A+R \mapsto A'+H'} from {n+Mk} completely random bits to {n+O(|S|) + M(k-C+O(1))} bits (recall that {A} and {R} were chosen randomly, and independently of each other). But since {n+Mk} random bits cannot be compressed losslessly into any smaller space, we have the entropy bound

\displaystyle  n+O(|S|) + M(k-C+O(1)) \geq n+Mk \ \ \ \ \ (1)

which leads to a contradiction if {M} is large enough (and if {C} is larger than an absolute constant). This proves Theorem 1.

Remark 1 Observe that the above argument in fact gives an explicit bound on {M}, and with a small bit of additional effort, it can be converted into a probabilistic algorithm that (with high probability) computes a satisfying assignment for {S} in time polynomial in {|S|} and {n}.

Remark 2 One can replace the usage of randomness and Shannon entropy in the above argument with Kolmogorov complexity instead; thus, one sets {A+R} to be a string of {n+Mk} bits which cannot be computed by any algorithm of length {n+O(|S| \log |S|) + M(k-C+O(1))}, the existence of which is guaranteed as soon as (1) is violated; the proof now becomes deterministic, except of course for the problem of building the high-complexity string, which by their definition can only be constructed quickly by probabilistic methods. This is the approach taken by Fortnow.