## General Satisfiability $ (x \vee y \vee z) (x \vee \bar{y}) (y \vee \bar{z}) (z \vee \bar{x}) (\bar{x} \vee \bar{y} \vee \bar{z}) $ - goal is to satisfy a boolean formula in conjunctive normal form (CNF) - collection of clauses with ORS them - literals: either a Boolean variable i.e $x$, or the negation of one i.e $\bar{x}$ - goal is to assign True or False to each variable so that every clause is true ## 3 Satisfiability - 3 satisfiability is where you have 3 clauses - 3-SAT and above are [[NP Complete Problems]] - problem: - input is a CNF with 3 clauses - you have to output an assignment of variables that satisfies all 3 clauses, or if no such solution exists we have to say so https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf