Gaurav
Gaurav

Reputation: 11

Find the class of the problem PP1 and PP2 using the information given below

Assume that P1, P2,..., Pn are 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. Please clarify my doubt.

Upvotes: 1

Views: 159

Answers (0)

Related Questions