GATE CSE 2003 | Question: 12

Question

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

Comments

https://gateoverflow.in/903/gate2003-12

---

we cannot say from shyam's reduction that  Π is in NP.....

as  Π can be np-hard also and every np-hard is not np

---

Out of syllabus

Answer 1

C. For a problem to be NP-Complete, it must be NP-hard and it must also be in NP.

Ram's reduction shows that $\Pi$ is NP hard because it must be at least as hard as $3$-SAT which is a known NP-Complete problem. Here, $\Pi$ need not be NP-Complete.

Now, Shyam's reduction shows that $3$-SAT problem is at least as hard as $\Pi$ or equivalently $\Pi$ is not harder than $3$-SAT. Since $3$-SAT is in NP, $\Pi$ must also be in NP.

Thus, $\Pi$ is NP-hard and also in NP $\implies$ $\Pi$ is NP-Complete.

Comments

but it   is not given that pi is in np

---

it is not given that $\Pi$ is in NP  that's why we can't say that $\Pi$ is in $NPC$ from Ram's statement. it must be in $NP-Hard$. If we have to show  $\Pi$ is in $NPC$ then we must have to prove that it will be in NP which is proved by Shyam's statement in the given question.

---

"If P1 is NP-complete, and there is a polynomial time reduction of P1 to P2, then P2 is NP-complete."

 In reducibility concept CLRS book never make this statement i guess ! Is this is an authentic statement of any lecture, i never come across such statement so please anyone confirm whether it's a valid statements or not ?

and  moreover, the first cond: ( 3-SAT(NPC) => II ) makes it NPH,

but second cond: (II => 3-SAT) never mean II is in P/NP correct me if i'm wrong? 

Answer 2

π is NP-C. 

Comments

Answer should be A because in Ram's case he is converting 3-SAT problem which is NP-complete problem to $\prod$. So from this we can conclude that a problem which is in NP (as 3-SAT is NP-complete so it must be NP ) is converted to a problem $\prod$ in polynomial time. From Ram's we derive that $\prod$ is NP-Hard.

Now coming to Shyam's case he has converted $\prod$ to NP-complete problem, which is useless. This is because here we have taken a problem $\prod$ and converted to well known NP-complete problem in polynomial time.

So we conclude that $\prod$ is NP-Hard only.

Answer 3

ans is A as  second condition doesn't imply that II is in NP same way as NP problem reduced to NP hard doesn't imply that  problem is NP hard