2. We talked in class about the complexity classes P and NP together with the concept of polynomial reductions being used to define the hardest problems in NP (that is, the NP- complete problems). The concept of complete problems is not restricted to these classes, but can be defined for any pair of classes. and Y such that CY as follows: • A problem л is Y-hard iff for all π' = Y it holds that л' ≤ л. • A problem л is Y-complete iff π is Y-hard and л ε Y. You will notice that the only missing piece is the definition of the ☐ reduction. Define a suitable reduction to be used in the definition above. Explain carefully how your reduction is suitable for the purpose.

2. We talked in class about the complexity classes P and NP together with the concept of polynomial reductions being used to define the hardest problems in NP (that is, the NP- complete problems). The concept of complete problems is not restricted to these classes, but can be defined for any pair of classes. and Y such that CY as follows: • A problem л is Y-hard iff for all π' = Y it holds that л' ≤ л. • A problem л is Y-complete iff π is Y-hard and л ε Y. You will notice that the only missing piece is the definition of the ☐ reduction. Define a suitable reduction to be used in the definition above. Explain carefully how your reduction is suitable for the purpose.