Constructive Lovasz Local Lemma [Bec'91,Alo'91,MR'98,CS'00,Mos'09,MT'10,KM'11,HSS'11,HS'17,HS'19] 。CSP instanceΦ=(V,C)with solution set∑ Each variable v is uniform in Individual falsifying probability:p()=max Pr[c is False] ·Degree:△（Φ）=max#{c'∈C|vbl(c)nvbl(c)≠o} ·fe·p(Φ)·△（Φ）≤l,then we can find some o∈ in probabilistic linear time or in deterministic polynomial timeConstructive Lovász Local Lemma [Bec’91, Alo’91, MR’98, CS’00, Mos’09, MT’10, KM’11, HSS’11, HS’17, HS’19] • CSP instance Φ = 𝑉,𝐶 with solution set Σ • Each variable 𝑣 is uniform in Ω𝑣 • Individual falsifying probability: 𝑝 Φ = max 𝑐∈𝐶 Pr[𝑐 is 𝐅𝐚𝐥𝐬𝐞] • Degree: Δ Φ = max 𝑐∈𝐶 # 𝑐 ′ ∈ 𝐶 vbl 𝑐 ∩ vbl 𝑐 ′ ≠ ∅ • If 𝑒 ⋅ 𝑝 Φ ⋅ Δ Φ ≤ 1, then we can find some 𝜎 ∈ Σ • in probabilistic linear time • or in deterministic polynomial time