# NP-Complete - NP: verifiable in polynomial time - If a decision problem is hard, the optimization is no easier. - Reduction - Prove NP-hard: find another NP-hard problem, and create polynomial conversion back and forth - Abstract problems - Set of _instances_ $I$ and set of _solutions_ $S$, _encoding_ $e: I \to \{0, 1\}^*$. - Cook's theorem - The satisfiability (SAT) is NP-Complete. - Given a boolean expression, find assignment of values to variables, so that the expression has value of 1 - CNF = Conjunctive Normal Form, each clause has at most 3 terms. - k-clique problem - k-clique is in NP (easy, done) - k-clique is in NP-hard - Create $G = (V, E)$ as follows - For each appearance of a variable in Expression as a vertex - For vertices which form complements of a variable, no edge connects them - Connect all other pairs of vertices by edges --- $G' = G$, $d = k$,