Q. 81 Ram and Shyam have been asked to show that a certain problem P is NPcomplete.
Ram shows a polynomial time reduction from the 3-SAT problem to P
, and Shyam shows a polynomial time reduction from P to 3-SAT. Which of the
following can be inferred from these reduction?
(A) P is NP-hard but not NP-complete
(B) P is in NP, but is not NP-complete
(C) P is NP-complete
(D) P is neither Np-hard, nor in NP
Answer: (C)
Explanation:
