![Mcqmate logo](https://mcqmate.com/images/logos/logo-black.png)
![Mcqmate logo](https://mcqmate.com/images/logos/logo-white.png)
McqMate
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 |
Answer» C. P3 is NP complete if P2 is reducible to P3 |
View all MCQs in
Theory of ComputationNo comments yet