Assume that P1, P2,..., Pn are all NP-class problems. PP1 and PP2 are unknown problems (i.e., we don't know whether they belong to the P or NP classes). If "P1, P2,...., Pn" problems can be reduced to PP1 in polynomial time, then PP1 can be reduced to PP2, and PP2 can be reduced to another NP problem in polynomial time. Specify the PP1 and PP2 classes with clear justification?
This was the question asked in one of my algorithms exam. I thought the answer for both the problems would be NP-hard, the logic which I thought of is that since all P1, P2, ...., Pn are NP problems and using the definition of NP-hard we can derive that PP1 is NP-Hard. After this for finding the class of PP2, since PP1 can be reduced to PP2. Therefore, we can say that PP2 is also NP-Hard.
The next bit of the question mentions about PP2 further being reducible to a NP problem but I don't feel that this information would be useful in finding the class of PP2. Let's assume the problem after reducing PP2 is some 'X' problem. This 'X' problem would be NP-Complete because it is NP-hard and NP as well.
My teacher says that PP1 is NP-Hard and PP2 is NP-Complete. According to him PP2 is NP- Complete because it is reduced to a NP problem but my doubt is how does this prove that PP2 is a NP problem. Please clarify my doubt.