Constraint Satisfaction Problem Φ=(V,Q,C) Variables:V={,..}with finite domains ... (local)Constraints:C=[C1,C2,...,Cm} each cC is defined on a subset vbl(c)of variables c:⑧g,→{True,False} iEvbl(c) ·CSP formula:Hx∈Q1×Q2×…×2n x)=∧c(o Example (k-SAT):Boolean variables V=[x1,x2.x3x,} k-CNFΦ=(：1VxV)A(x1VVx4)AxVx4Vx5) clause• Variables: with finite domains • (local) Constraints: • each is defined on a subset vbl(c) of variables • CSP formula: • Example (k-SAT): Boolean variables V = {x1, x2,…, xn} Q1,…, Qn C = {c1, c2,…, cm} c ∈ C c : i∈ ⨂ 𝗏𝖻𝗅(c) Qi → {𝚃𝚛𝚞𝚎, 𝙵𝚊𝚕𝚜𝚎} ∀x ∈ Q1 × Q2 × ⋯ × Qn Φ(x) = ⋀ c∈C c (x𝗏𝖻𝗅(c)) V = {x1, x2, x3, x4, x5} Φ = (x1 ∨ ¬x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x3 ∨ ¬x4 ∨ ¬x5) Constraint Satisfaction Problem Φ = (V, Q,C) k-CNF clause