Q12

MCQ1 mark, −0.25

Ram and Shyam have been asked to show that a certain problem $\Pi$ is $\text{NP-complete}.$ Ram shows a polynomial time reduction from the $\text{3-SAT}$ problem to $\Pi$ , and Shyam shows a polynomial time reduction from $\Pi$ to $\text{3-SAT.}$ Which of the following can be inferred from these reductions?

(A)

$\Pi$ is NP-hard but not NP-complete

(B)

$\Pi$ is in NP, but is not NP-complete

(C)

$\Pi$ is NP-complete

(D)

$\Pi$ is neither NP-hard, nor in NP

Loading…