Problem. 3SAT [3SAT] Definition 1. Conjunctive Normal Form [cnf] A problem is in conjunctive normal form (CNF) if it is a product of sums: i.e. an AND of ORs. Example. 3SAT\text{3SAT} 3SAT={⟨φ⟩:φis a Boolean formula in CNF with 3 literals per clause for which there exists a satisfying truth assignment}\text{3SAT} = \left\{ {\left\langle \varphi \right\rangle:\varphi\ \text{is a Boolean formula in CNF with 3 literals per clause for which there exists a satisfying truth assignment}} \right\} e.g. (x1∨¬x2∨x3)∧(x5∨x4∨¬x2)∧(¬x4∨x1∨x3)∧(¬x3∨x2∧¬x1)\left( {x_{1} \vee \neg x_{2} \vee x_{3}} \right) \land \left( {x_{5} \vee x_{4} \vee \neg x_{2}} \right) \land \left( {\neg x_{4} \vee x_{1} \vee x_{3}} \right) \land \left( {\neg x_{3} \vee x_{2} \land \neg x_{1}} \right)