Ram and Shyam have been asked to show that a certain problem Π is NP-complete.…
2003
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 Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
- A.
Π is NP-hard but not NP-complete
- B.
Π is in NP, but is not NP-complete
- C.
Π is NP-complete
- D.
Π is neither NP-hard, nor in NP
Attempted by 7 students.
Show answer & explanation
Correct answer: C
Ram's reduction from 3-SAT to Π shows that Π is NP-hard, as any problem in NP can be reduced to it via 3-SAT. Shyam's reduction from Π to 3-SAT implies that Π is in NP, since 3-SAT is in NP and polynomial-time reductions preserve membership. Together, these two reductions confirm that Π is both NP-hard and in NP, which defines NP-completeness. Therefore, the correct inference is that Π is NP-complete.
A video solution is available for this question — log in and enroll to watch it.