Advanced Algorithms Lovasz Local Lemma 尹一通Nanjing University,2022Fall
尹⼀通 Nanjing University, 2022 Fall Advanced Algorithms Lovász Local Lemma
k-SAT Conjunctive Normal Form(CNF): Liberals Φ=xVV)∧1VV4∧③V V7x5) clause Boolean variables:x1,x2,...,{True,False} k-CNF:each clause contains exactly k variables Problem(k-SAT) Input:k-CNF formula Output:determine whether is satisfiable. 。[Cook-Levin]NP-hard if k≥3
• Conjunctive Normal Form (CNF): Boolean variables: • -CNF: each clause contains exactly variables • [Cook-Levin] NP-hard if Φ = (x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x3 ∨ ¬x4 ∨ ¬x5) x1, x2,…, xn ∈ {𝚃𝚛𝚞𝚎, 𝙵𝚊𝚕𝚜𝚎} k k k ≥ 3 k-SAT clause literals Problem ( -SAT) Input: -CNF formula . Output: determine whether is satisfiable. k k Φ Φ
Trivial Cases Problem (k-SAT) Input:k-CNF formula Output:determine whether is satisfiable. Clauses are disjoint: Φ=(x1V2Vx3)Λ(x4Vx5Vx6)Λ(xV7 Xs VX9). resolve each clause independently(is alwsays satisfiable!) 。m<2k=Φis always satisfiable. m:of clauses
Problem ( -SAT) Input: -CNF formula . Output: determine whether is satisfiable. k k Φ Φ • Clauses are disjoint: resolve each clause independently (Φ is always satisfiable!) • ⟹ is always satisfiable. Φ = (x1 ∨ ¬x2 ∨ x3) ∧ (x4 ∨ x5 ∨ x6) ∧ (x7 ∨ ¬x8 ∨ ¬x9) m < 2k Φ Trivial Cases m: # of clauses
The Probabilistic Method 。k-CNF:Φ=C1∧C2∧…∧Cm k variables Φ=(x1V7x2V3)∧(x1Vx2Vx4)Λ(5Vx4Vx5) Draw uniform random x1,x2,...,{True,False} Bad event A;:clause C;is violated V1≤i≤m,Pr[A=2-k ·Union bound:PrVA≤∑,PrAl=m2-t m<2k→pr八>0→is satisfiable: →r△-ia-m>o (independent bad events)
• -CNF: • Draw uniform random • Bad event : clause is violated • Union bound: disjoint clauses k Φ = C1 ∧ C2 ∧ ⋯ ∧ Cm Φ = (x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x3 ∨ ¬x4 ∨ ¬x5) x1, x2, …, xn ∈ {𝚃𝚛𝚞𝚎, 𝙵𝚊𝚕𝚜𝚎} Ai Ci ∀1 ≤ i ≤ m, Pr[Ai ] = 2−k m < 2k ⟹ Pr [ m ⋀ i=1 Ai ] > 0 ⟹Pr [ m ⋀ i=1 Ai ] = m ∏ i=1 (1 − Pr[Ai ]) > 0 The Probabilistic Method k variables (independent bad events) ⟹ ⟹Φ is satisfiable! Pr [⋁m i=1Aj] ≤ ∑m i=1 Pr[Ai ] = m2−k
The Probabilistic Method Problem(k-SAT) Input:k-CNF formula Output:determine whether is satisfiable. ③WILEY ·uniform random x1,.,xm∈{True,False} disjoint clauses or →Pr[Φ(x)=True]>0 THE PROBABILISTIC m <2k METHOD 3x∈{T,F}m Third Edition → Φ(x)=True Noga Alon The Probabilistic Method: Joel H.Spencer Draw x from prob.space for property, Pr[g(x)]>0→3x∈2,(x) wiley-interscience Series in Discrete Mathematics and Optimization
• uniform random x1, …, xn ∈ {𝚃𝚛𝚞𝚎, 𝙵𝚊𝚕𝚜𝚎} The Probabilistic Method disjoint clauses or m < 2k } ⟹ Pr[ Φ(x) = 𝚃𝚛𝚞𝚎 ] > 0 ∃x ∈ {𝚃, 𝙵}n ⟹ Φ(x) = 𝚃𝚛𝚞𝚎 The Probabilistic Method: Draw x from prob. space Ω: for property 𝒫, Pr[𝒫(x)] > 0 ⟹ ∃x ∈ Ω, 𝒫(x) Problem ( -SAT) Input: -CNF formula . Output: determine whether is satisfiable. k k Φ Φ