Lovasz Local Lemma 上午：尹一通（南京大学） 下午：何昆（中科院计算所） “计算理论之美”暑期学校2021年7月9日
Lovász Local Lemma “计算理论之美”暑期学校 2021年7月9日 上午： 尹⼀通（南京⼤学） 下午： 何昆（中科院计算所）
k-SAT Conjunctive Normal Form(CNF): Literals 7 Φ=(K1VV)Λ(xVVx4∧⑤ X4) /7x5) clause Boolean variables:x1,2,...,{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: Φ=(x1Vx2V3)Λ(x4Vx5Vx6)Λ(x7 VXs V-1X9). 00)00)o00) resolve each clause independently(is always 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 Φ=(x1Vx2V3)Λ(x1Vx2Vx4)Λ(3Vx4Vx5 ·Draw uniform randomx,2,,xn∈{True,False} Bad event A;:clause C;is violated V1≤i≤m,Pr[A]=2-k ·Union bound:Pr VA≤∑，PrAl=m2-t m<2→n人>0→issatisfable! iec阳5→r-ia-w>01 (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,,x,∈{True,False} disjoint clauses or →Pr[Φ(x)=True]>0 THE m<2k PROBABILISTIC METHOD 3x∈{T,F}” Third Edition → Φ(x)=True Noga Alon The Probabilistic Method: Joel H.Spencer Draw x from prob.space for property, Pr[(x)]>0→3x∈2，(x) www. ley-interscience Series in Discreto H
• 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 Φ Φ