SAT ■3SAT: ▣1 m variables:x1,…,xn∈{0,1} ▣ m clauses:OR of exactly 3 variables or their negations ■e.g.x1Vx2Vx3 x=10010 CNF formula:AND of these m clauses ■E.g.中=(Vx2Vx3)∧(x2Vx4Vx5)∧(x1Vx3Vx5) 3SAT Problem:Is there an assignment of variables x s.t.the formula o evaluates to 1? i.e.assign a 0/1 value to each xi to satisfy all clauses. 4SAT ◼ 3SAT: ❑ 𝑛 variables: 𝑥1,… , 𝑥𝑛 ∈ 0,1 ❑ 𝑚 clauses: OR of exactly 3 variables or their negations ◼ e.g. 𝑥1 ∨ 𝑥2 ∨ 𝑥3 ❑ CNF formula: AND of these 𝑚 clauses ◼ E.g. 𝜙 = 𝑥1 ∨ 𝑥2 ∨ 𝑥3 ∧ 𝑥2 ∨ 𝑥4 ∨ 𝑥5 ∧ 𝑥1 ∨ 𝑥3 ∨ 𝑥5 ◼ 3SAT Problem: Is there an assignment of variables 𝑥 s.t. the formula 𝜙 evaluates to 1? ❑ i.e. assign a 0/1 value to each 𝑥𝑖 to satisfy all clauses. 4 𝑥 = 10010