Lovasz Local Lemma(LLL) ·(k,d)-CNF:Φ=(x1Vx2V3)∧(x1Vx2Vx4)A(x3Vx4Vx5) constraint width =k variable degree sd ·Uniform random X1,X,,Xn∈{True,False} Violation probability:p=2-k ·Dependency degree:D≤dk ·LLL:k之logd (k≥1og2d+log2k+O(1) LLL epD≤edk2-k≤1 a SAT solution exists Moser-Tados and can be found in O(dkn)timeLovász Local Lemma (LLL) • (k, d)-CNF: • Uniform random • Violation probability: • Dependency degree: • LLL: ( ) Φ = (x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x3 ∨ ¬x4 ∨ ¬x5) X1, X2, …, Xn ∈ {𝚃𝚛𝚞𝚎, 𝙵𝚊𝚕𝚜𝚎} p = 2−k D ≤ dk k ≳ log d k ≥ log2 d + log2 k + O(1) c1 c2 c3 x1 x2 x3 x4 x5 constraint width = k variable degree ≤ d a SAT solution exists and can be found in O(dkn) time epD ≤ edk2−k ≤ 1 LLL Moser-Tados