Consider three problems P1, P2 and P3. It is known that P1 has polynomial time solution and P2 is NP-complete and P3 is in NP. Which one of the following is true.
A)P3 has polynomial time solution if P1 is polynomial time reducible to P3
B)P3 is NP complete if P3 is polynomial time reducible to P2
C)P3 is NP complete if P2 is reducible to P3
D)P3 has polynomial time complexity and P3 is reducible to P2

Question

Quizplus · Accepted Answer

For a problem P3 to be NP-complete, two conditions must be satisfied: P3 must be in NP (which is given), and all problems in NP must be polynomial time reducible to P3. Since P2 is NP-complete, it represents the class of problems that are the hardest in NP. If P2 can be reduced to P3 in polynomial time, it means P3 is at least as hard as P2, satisfying the second condition for NP-completeness. Thus, P3 is NP-complete if P2 is reducible to P3.

Consider Three Problems P1, P2 and P3