- [[Coping With NP Complete Problems]] - [[Traveling Salesman Problem (TSP)]] - [[3SAT Problem]] - [[Independent Set Problem]] - [[Vertex Cover Problem]] - [[Clique Problem]] - [[Set Cover Problem]] - [[Hamiltonian Path]] - [[Hamiltonian Cycle]] - a search problem is NP complete if all other search problems reduce to it - NP complete algorithms can be solved by *some* algorithm, but unfortunately this algorithm will be exponential - *difficulty* flows in the direction of reduction - since all other search problems reduce to a NP complete problem, each NP complete problem contains the complexity of *all* search problems - if even one NP complete problem in P, then $P = NP$ - how to prove problem $A$ is NP complete: 1. show $A$ is in NP by designing a verification algorithm 2. choose an NP complete problem $B$, then show that $A$ is NP hard by reducing $B$ to $A$ 3. 1 & 2 shows that $A$ is NP complete - let reduction of $A$ to $B$ be denoted by $A \to B$ - ($A \to B$ and $B \to C$) $\implies$ $A \to C$ https://people.eecs.berkeley.edu/~vazirani/algorithms/chap8.pdf