Constraint Satisfaction Problem ●variables:x1,x2,,xn∈D(domain) constraints:C1,C2,....Cm ●where C(ri,ri2,)∈{true,false} CSP solution:an assignment of variables satisfying all constraints examples:SAT,graph colorability,... existence:When does a solution exist? search:How to find a solution?
Constraint Satisfaction Problem • variables: x1, x2, ..., xn ∈ D (domain) • constraints: C1, C2, ..., Cm • where • CSP solution: an assignment of variables satisfying all constraints • examples: SAT, graph colorability, ... • existence: When does a solution exist? • search: How to find a solution? Ci(xi1 , xi2 ,...) 2 {true, false}
The Probabilistic Method CSP C1,C2,...Cm defined onx1,x2....xn sampling random values ofx1,x2,..., Bad event Ai:constraint Ci is violated None of the ad troPr The probabilistic method:being good is possible >0 Pr i=1
The Probabilistic Method • sampling random values of x1, x2, ..., xn • Bad event Ai: constraint Ci is violated • None of the bad events occurs with prob: • The probabilistic method: being good is possible Pr" ^ m i Ai # Pr" ^ m i=1 Ai # > 0 CSP C1, C2, ..., Cm defined on x1, x2, ..., xn
Dependency Graph events:A1,A2,...,Am dependency graph:D(V,E) V={1,2,,m} 访∈E> Ai and Aj are dependent d:max degree of dependency graph A2 A1(X1,X4) A1 A4(X4) A3 A2(X1,X2) A5(X3) A3(X2,X3) A5 A4 X1,...,X4 mutually independent
A1 A2 A3 A5 A4 X1,...,X4 mutually independent A1(X1,X4) A2(X1,X2) A3(X2,X3) A4(X4) A5(X3) events: A1, A2, ... , Am d : max degree of dependency graph dependency graph: D(V,E) V = { 1, 2, ..., m } ij ∈E Ai and Aj are dependent Dependency Graph
events:A1,A2,...,Am each event is independent of all but at most d other events Lovasz Local Lemma(symmetric) 。Vi,PrLA≤p Pr >0 ep(d+1)≤1 i=】 Lovasz Local Lemma(general) 3a1,..,am∈[0,1) i,PrA≤aaI1-a) →m公 i三1 j心i
events: A1, A2, ... , Am each event is independent of all but at most d other events 9↵1,..., ↵m 2 [0, 1) 8i,Pr[Ai] ↵i Y j⇠i (1 ↵j ) Pr " ^ m i=1 Ai # Y m i=1 (1 ↵i) Lovász Local Lemma (general) • ∀i, Pr[Ai] ≤ p • ep(d + 1) ≤ 1 Pr" ^ m i=1 Ai # > 0 Lovász Local Lemma (symmetric)
k-SAT .n Boolean variables:x1,x2,...,xnEtrue,false} conjunctive normal form: k-CNFΦ=C1∧C2∧·∧Cm “ils satisfiable?' ·n clauses::Cl,C2,,Cm .each clause Ci=iveiv...vli is a disjunction of k distinct literals ·each literal::lj∈{xr,xr}for some r degree d:each clause shares variables with at most d other clauses
k-SAT • n Boolean variables: x1,x2,...,xn 2 {true, false} • m clauses: C1,C2,...,Cm • each clause Ci = `i1 _`i2 _···_`ik • each literal: for some r • degree d : is a disjunction of k distinct literals `j 2 {xr ,¬xr } each clause shares variables with at most d other clauses k-CNF ¡ = C1 ^C2 ^···^Cm • conjunctive normal form: “Is φ satisfiable?