Constraint Satisfaction Problem(CSP) Variable set V:Each v E V takes values in domain ·Constraint set C:Each c∈C is a constraint on vbl(c)∈V c:,→{True,False} vEvbl(c) Solution set Each o Eve such that all constraints are satisfied Atomic condition:Each constraint has exactly one falsifying assignment Examples: .CNF formula:=(x1 Vx2 Vx3)A (x2 Vx7)A (x3 Vx4) Hypergraph coloring:color vertices of a hypergraph without monochromatic hyperedgeConstraint Satisfaction Problem (CSP) • Variable set 𝑉: Each 𝑣 ∈ 𝑉 takes values in domain Ω𝑣 • Constraint set 𝐶: Each 𝑐 ∈ 𝐶 is a constraint on vbl(𝑐) ⊆ 𝑉 𝑐: ෑ 𝑣∈vbl(𝑐) Ω𝑣 → {𝐓𝐫𝐮𝐞,𝐅𝐚𝐥𝐬𝐞} • Solution set Σ: Each 𝜎 ∈ Σ ⊆ ς𝑣∈𝑉 Ω𝑣 such that all constraints are satisfied • Atomic condition: Each constraint has exactly one falsifying assignment Examples: • CNF formula: Φ = 𝑥1 ∨ ¬𝑥2 ∨ 𝑥3 ∧ 𝑥2 ∨ 𝑥7 ∧ ¬𝑥3 ∨ ¬𝑥4 • Hypergraph coloring: color vertices of a hypergraph without monochromatic hyperedge