Source-linked AI summary
A constructive proof of the Lovasz Local Lemma
Robin A. Moser
TL;DR
The paper addresses the lack of efficient algorithms for finding satisfying assignments guaranteed by the Lovasz Local Lemma. It develops a constructive analysis and proves randomized and fixed-k deterministic algorithms at the asymptotic optimum neighbourhood bound.
Problem
Earlier proofs established existence but did not disclose an efficient polynomial-time method for finding satisfying assignments to sparse k-CNF formulas.
Method
The paper uses local corrections, assignment tables, and composite-witness encoding and counting to analyze a constructive satisfiability procedure.
Results
Under |Γ+_F(C)| ≤ 2^(k-5), a randomized algorithm finds a satisfying assignment in expected time polynomial in |F| independently of k; for fixed k, a deterministic polynomial-time variant exists.
Takeaways & Limitations
The results provide a constructive proof route for the Local Lemma at its asymptotic optimum neighbourhood threshold.
Takeaways & Limitations
The deterministic polynomial-time guarantee is stated only when k is a fixed constant, while the randomized guarantee is the one independent of k.
Abstract
from arXiv · showhide
The Lovasz Local Lemma [EL75] is a powerful tool to prove the existence of combinatorial objects meeting a prescribed collection of criteria. The technique can directly be applied to the satisfiability problem, yielding that a k-CNF formula in which each clause has common variables with at most 2^(k-2) other clauses is always satisfiable. All hitherto known proofs of the Local Lemma are non-constructive and do thus not provide a recipe as to how a satisfying assignment to such a formula can be efficiently found. In his breakthrough paper [Bec91], Beck demonstrated that if the neighbourhood of each clause be restricted to O(2^(k/48)), a polynomial time algorithm for the search problem exists. Alon simplified and randomized his procedure and improved the bound to O(2^(k/8)) [Alo91]. Srinivasan presented in [Sri08] a variant that achieves a bound of essentially O(2^(k/4)). In [Mos08], we improved this to O(2^(k/2)). In the present paper, we give a randomized algorithm that finds a satisfying assignment to every k-CNF formula in which each clause has a neighbourhood of at most the asymptotic optimum of 2^(k-5)-1 other clauses and that runs in expected time polynomial in the size of the formula, irrespective of k. If k is considered a constant, we can also give a deterministic variant. In contrast to all previous approaches, our analysis does not anymore invoke the standard non-constructive versions of the Local Lemma and can therefore be considered an alternative, constructive proof of it.
1 Introduction
The paper develops constructive algorithms for satisfying sparse k-CNF formulas, addressing the non-constructive nature of earlier Local Lemma proofs. It reaches the asymptotic optimum neighbourhood bound while providing randomized and, for fixed k, deterministic procedures.
- Background: The Lovasz Local Lemma guarantees satisfiability when each clause shares variables with at most 2^(k-2) other clauses.A formula is satisfiable when some truth assignment satisfies every clause.
- Motivation: Earlier Local Lemma proofs did not provide an efficient method for finding a satisfying assignment, leaving constructive search as an open problem.Beck later gave a polynomial-time algorithm under the stricter condition |ΓF(C)| ≤ 2^(k/48).
- Contribution: The paper presents its analysis as an alternative constructive proof of the Local Lemma rather than invoking the standard non-constructive versions.Its approach builds on tools derived from Beck's method and later randomization-based improvements.
- Main randomized result: The paper proves satisfiability and gives a randomized algorithm with expected running time polynomial in |F|, independent of k, when |Γ+_F(C)| ≤ 2^(k-5).The bound applies to every clause C in the k-CNF formula.
- Deterministic variant: For fixed constant k, the procedure can be derandomized into a deterministic algorithm running in time polynomial in |F|.The deterministic guarantee is stated separately from the randomized result.
2 A randomized algorithm based on local corrections
The solver repeatedly repairs violated clauses through randomized local corrections, organizing recursive calls lexicographically and aborting unusually long corrections. Its analysis shows that completed corrections preserve satisfaction of the relevant local subformula and that the overall loop uses polynomially many steps apart from rare restarts.
- Local-correction procedure: The procedure starts from a random assignment and recursively applies local corrections to violated clauses near the clause currently being repaired.The recursive procedure replaces the variables of the selected clause by fresh random values and continues on violated clauses in its inclusive neighbourhood.
- Local-correction procedure: Clauses are selected in a fixed lexicographic order, and each correction is aborted after more than log m + 2 recursive invocations.The complete solver repeatedly invokes the correction routine on the lexicographically first violated clause and restarts if the invocation limit is exceeded.
- Randomness representation: The assignment-table representation replaces each resampling by incrementing an indirect assignment index, while preserving the distribution of fresh random values.A random table supplies independent entries, and each variable uses a previously unused entry when its indirect value increases.
- Recursion trees: A recursion tree records the clauses handled by recursive calls, with each child labelled by a clause in the parent’s inclusive neighbourhood.The natural depth-first ordering reconstructs the invocation order and prevents identically labelled siblings.
- Correctness: When a correction halts, its output satisfies every clause whose variables occur in the recursion tree.The last recursive invocation sharing variables with a potentially violated clause guarantees that clause is satisfied when the procedure returns.
- Running time: The outer loop repeats at most O(m) corrections because each completed correction eliminates at least one violated clause, while the remaining analysis bounds costly aborts.The algorithm’s polynomial-time claim reduces to showing that restarts occur only a polynomial number of times in expectation.
3 Consistency and composite witnesses
The analysis encodes random correction histories through consistency with a shared assignment table and combines overlapping recursion trees into composite witnesses. A failed long correction yields a large consistent witness, whose fixed-witness probability is exponentially small in its size.
- Consistency: An indirect assignment induces a standard assignment by selecting the table entry indexed by each variable’s indirect value.This representation lets the analysis describe all resampling events using one globally fixed random assignment table.
- Consistency: A recursion tree is consistent with an assignment table offset by an indirect assignment when every recorded literal evaluates to 0 at its indexed table entry.The offset accounts for the variable values present when the recursive invocation begins.
- Composite witnesses: Composite witnesses are connected collections of recursion trees whose trees share variables, with vertices ordered tree-by-tree and occurrence indices tracking prior appearances of each variable.The auxiliary graph connects two trees exactly when their variable sets intersect.
- Composite witnesses: Consistency of a composite witness decomposes into consistency of its component trees under the appropriate offsets.The decomposition follows from the ordering of the trees and the induced offset assignments.
- Probability bound: A fixed composite witness of size |V(W)| is consistent with a random assignment table with probability exactly 2^(-k|V(W)|).The witness checks k|V(W)| distinct table entries, each of which must take a prescribed value.
- Failure certificates: If the solver aborts after log m + 2 recursive invocations, the failed run certifies a large composite witness consistent with the assignment table.The witness contains the interrupted recursion tree together with the connected component of overlapping trees, allowing rare bad runs to be counted.
4 Encoding and counting composite witnesses
Composite witnesses are reversibly encoded as coloured subtrees of an infinite rooted tree, yielding a bound on their number. Combined with their exponentially small consistency probability, this proves that large consistent witnesses occur with probability at most 1/2.
- Encoding: Witness encodings represent a composite witness by a root clause, a rooted subtree of an infinite (2d)-ary tree, and a 2-colouring of its edges.The tree is embedded into the formula’s dependency structure so child labels represent possible inclusive-neighbourhood clauses.
- Counting: For witnesses of size u, the number of distinct composite witnesses is at most m · 2^(u(k−1)).The bound follows by choosing a root clause, counting rooted subtrees, and counting edge colourings.
- Encoding: Each recursion tree can be reversibly embedded as a subtree of the labelled infinite tree, and the complete composite witness can be glued into one such subtree.Reversibility permits counting encodings instead of composite witnesses directly.
- Probability bound: Because a fixed size-u witness is consistent with probability 2^(-ku), the counting bound makes large consistent witnesses sufficiently unlikely.The expected number of consistent large witnesses is bounded by summing over their sizes.
- Probability bound: The probability that any large composite witness is consistent with a uniformly random assignment table is at most 1/2.Consequently, at least half of assignment tables contain no consistent large witness.
- Conclusion: This probability estimate completes the proof of the paper’s main theorem.The witness-counting argument supplies the missing bound needed for the solver’s expected running-time analysis.
5 A deterministic variant
The deterministic variant replaces random assignment-table sampling with systematic enumeration and deterministic search, using a witness-size lemma to reduce the checks to polynomially many cases.
- 5 A deterministic variant: For constant k, the randomized procedure can be derandomized by enumerating relevant large composite witnesses and searching deterministically for an assignment table avoiding them.The approach is polynomial-time because only polynomially many relevant witnesses need to be considered.
- 5 A deterministic variant: Any consistent composite witness of size at least u implies one of size between u and ku + 1 that is equally consistent.This bounds the witness sizes that must be checked when detecting premature correction-procedure interruption.
- 5 A deterministic variant: The witness-size lemma follows by deleting the last vertex, selecting the largest remaining connected component, and preserving consistency while obtaining a smaller witness.Removing one clause can create at most k components because the clause contains exactly k variables.
- 5 A deterministic variant: It suffices to check composite witnesses with sizes in [log m + 2, k(log m + 2) + 1] for consistency with a candidate assignment table.The number of such witnesses is bounded polynomially in m, so they can be enumerated in polynomial time.
- 5 A deterministic variant: The deterministic construction encodes forbidden-witness avoidance as a CNF formula G and solves G after showing its expected number of violated clauses is below 1/2.This completes the proof of the deterministic variant.