in Algorithms edited by
5,397 views
15 votes

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?

  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

in Algorithms edited by
5.4k views

7 Comments

From the reduction of Ram, we can tell that ∏ is NP Hard. What can we infer from Shyam's reduction??
1
From Shyam's reduction  only we can tell that ∏ can't be harder than NPC. So it's in NP. right?
1
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.
0
Is this in syllabus now?
0
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.
2
0
we cannot say from shyam's reduction that  Π is in NP.....

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

Subscribe to GO Classes for GATE CSE 2022

3 Answers

13 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.
edited by

9 Comments

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?

3

from "http://quiz.geeksforgeeks.org/algorithms/np-complete/"-

 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??

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

@Mahesha999

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).

3
@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?
0
@habedo007

not atleat,but atmost..in such case L cant be harder than NP.
1
but it   is not given that pi is in np
0
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.
1

"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? 

0
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
0 votes

π is NP-C. 

1 comment

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.
0
Answer:

Related questions