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.

Mr. Dubey

🎓 Coach ⭐ 104.48K Points

📊 Theory of Computation

Q. 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

💬 Discuss

✅ Correct Answer: (C) P3 is NP complete if P2 is reducible to P3

You must be Logged in to update hint/solution

💬 Discussion

📊 Question Analytics

👁️

657

Total Visits

📽️

3 y ago

Published

🎖️

Mr. Dubey

Publisher

📈

93%

Success Rate

Mr. Dubey

💬 Discussion

Related MCQs

📊 Question Analytics