-
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a Polynomial time reduction from the 3-SAT problem to II, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions?
-
- Π is NP-hard but not NP-complete
- Π is in NP, but is not NP-complete
- Π is NP-complete
- Π is neither NP-hard, nor in NP
- Π is NP-hard but not NP-complete
Correct Option: C
Since, 3 SAT is reduced to Π, this implies 3 SAT ≤ Π and since, Π is reduced to 3 SAT, this implies π ≤ 3 SAT.
We know that, if L1 ≤ L2 and L1 is NP-complete, then L2 is also NP-complete. Since, 3 SAT is NP-complete so Π is also NP complete.
