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