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