SAT and k-SAT SAT formula:AND of m clauses n variables (taking values 0 and 1) a literal:a variable x;or its negationi m clauses,each being OR of some literals. SAT Problem:Is there an assignment of variables s.t.the formula evaluates to 1? k-SAT:same as SAT but each clause has at most k literals. SAT and k-SAT are in NP. Given any assignment,it's easy to check whether it satisfies all clauses. 5SAT and 𝑘-SAT ◼ SAT formula: AND of 𝑚 clauses ❑ 𝑛 variables (taking values 0 and 1) ❑ a literal: a variable 𝑥𝑖 or its negation 𝑥ഥ𝑖 ❑ 𝑚 clauses, each being OR of some literals. ◼ SAT Problem: Is there an assignment of variables s.t. the formula evaluates to 1? ◼ 𝑘-SAT: same as SAT but each clause has at most 𝑘 literals. ◼ SAT and 𝑘-SAT are in NP. ◼ Given any assignment, it’s easy to check whether it satisfies all clauses. 5