oblem P2. is a translation such that a so- lution for P3 can provide a solution for Pr. More precisely, if there is a polynomial-time reduction from Pr to P2, then a polynomial-time algorithm for Pz implies a polynomial-time algorithm for Pi. A given problem is NP-hard if for every problem in NP there