13 Hardness for the class NP

• Polytime reduction : We say that $Y{\le }_{\mathbf{P}}X$ if
  • The reduction takes polynomial time
  • $Y$ can be solved using (a black-box which solves) $X$
• We say that $Y$ is polytime reducible to $X$
• Definition : A problem $X$ is $\mathbf{NP}$-hard if for all problems $Y\in \mathbf{NP}$ we have $Y{\le }_{\mathbf{P}}X$
• How would you show $\mathbf{NP}$-hardness of a given problem, say SUDOKU ?
  • Show $Z{\le }_{\mathbf{P}}$ SUDOKU for some known $\mathbf{NP}$-hard problem $Z$
  • This is sufficient because for each $X\in \mathbf{NP}$ we already have $X{\le }_{\mathbf{P}}Z$
  • By transitivity, it follows that for each $X\in \mathbf{NP}$ we have $X{\le }_{\mathbf{P}}$ SUDOKU
• Great, except no one knew how to show the existence of a single $\mathbf{NP}$-hard problem!