The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 votes

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

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

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

  3. $\Pi$ is NP-complete

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

asked in Algorithms by Veteran (52k points)
edited by | 2.1k views
From the reduction of Ram, we can tell that ∏ is NP Hard. What can we infer from Shyam's reduction??
From Shyam's reduction  only we can tell that ∏ can't be harder than NPC. So it's in NP. right?
From Ram's reduction we can say that it is NP-HARD.

From Shyam's reduction we can say that it is in NP.

Hence it is NP complete.
Is this in syllabus now?
Strictly speaking "no", because no question referring to some known NP-complete problem can be asked as per current syllabus. But reduction is there in TOC.

This one ..

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

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

3 Answers

+10 votes
Best answer
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.
answered by Loyal (8.1k points)
edited by

Ram shows there is a polynomial reductin from 3-SAT to $\pi$. 3SAT is known to be NPC. And there is a theorem:

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

Ram's reduction actually directly shows that $\pi$ is indeed NP-comptete, not just NP-Hard. So we really dont need to consider what Shyam's reduction implies. From Ram's reduction alone, we can infer that $\pi$ is NPC.

Am I right with this? Or do we really need to consider implication of Shyam's reduction in order to come to the final conclusion? Can anyone please confirm?


from ""-

 The idea is to take a known NP-Complete problem and reduce it to L.  If polynomial time reduction is possible, we can prove that L is NP-Complete by transitivity of reduction (If a NP-Complete problem is reducible to L in polynomial time, then all problems are reducible to L in polynomial time).

So i think the first one itself proves that π is NPC. 

what is the significance of second one??

someone plzz have a look??

Ram's reduction shows $\pi$ is NP hard, but how shyam's reduction showed $\pi$ is NP?


Your definition of NP-complete is wrong.

Your definition is of NP-hard.(refer CLRS 3rd Edition pg no. 1069)

If $L \epsilon NP$

And $NP-complete \leq(polynomial-time) L$

Then only $L\epsilon NP-complete$.

and @habedo007 :If an Np complete problem is reduced from L ,then Lis at most NP hard(or equivalently) L is less hard (or equal in hardness) to NP complete.
Since any problem in NPC is atleast hard as any problem in NP,any problem less harder (or equally hard) to NP Complete is in NP(because no class easier than NP is separately defined).

@Ali Jazib Mahmood: You mean to say if a problem L is reducible to some NP-complete problem, then L qualifies (at least) as NP?

not atleat,but such case L cant be harder than NP.
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.
0 votes
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
answered by (37 points)
0 votes

π is NP-C. 

answered by (349 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,093 answers
71,001 users