14 The first NP-hard problem

Cook

CNF-Satisfiability (SAT) is $\mathbf{NP}$-hard

• If you believe $\mathbf{P}\ne \mathbf{NP}$ then
  • A problem being $\mathbf{NP}$-hard means it cannot be solved in polynomial time!
  • This is because : for every $X\in \mathbf{NP}$ we have $X{\le }_{\mathbf{P}}\text{SAT}$ and $\text{SAT}\in P$ $\Rightarrow$ $X\in \mathbf{P}$
• Karp (1972) showed 21 classical problems to be $\mathbf{NP}$-hard
• How do you show a problem, say $X$, is $\mathbf{NP}$-hard ?
  • Reduction from ant of the known $\mathbf{NP}$-hard problems, say SAT, to $X$
  • That is, $\text{SAT}{\le }_{\mathbf{P}}X$
  • Need to show how you can solve SAT using a black-box for $X$
  • ($\cdots$ plus polynomial overhead for the translation)
  • Note that the reduction should work in polytime
• Thousands of problems are now known to be $\mathbf{NP}$-hard!