Ram and Shyam have been asked to show that a certain problem Π is NP-complete.…
PYQ GATE 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 76 students.
Sign up free to check your answer
Sign up freeLoading lesson…

