GATE2006-16, ISRO-DEC2017-27

Question

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

• A. R is NP-complete
• B. R is NP-hard
• C. Q is NP-complete
• D. Q is NP-hard

Answer 1

Answer B.

As $S$ is $NPC$ i.e $NP$-$Hard$ and $NP$.

• We know that, if $NP$-$Hard$ problem is reducible to another problem in Polynomial Time, then that problem is also $NP$-$Hard$ which means every $NP$ problem can be reduced to this problem in Polynomial Time.

Therefore, $R$ is $NP$-$Hard$.

Now $Q$ is reduced to $S$ in polynomial time. 

• If $Q$ is reducible to $S$ in polynomial time, $Q$ could be $NP$ because all $NP$ problems can be reduced to $S.$ Since $Q$ could be $NP$ therefore $Q$ could be $P$ also as $P$ is subset of $NP$. Also $Q$ could be $NPC$ because every $NPC$ problem can be reduced to another $NPC$ problem in polynomial time. 

So, nothing can be concluded about $Q$.

Comments

why cant we say that R is NPC ? since S is polynomial time reducible to R .. and S is NPC.. then we can say that R is atleast as hard as S .. so why cant R  be NPC ?

and isnt it implicitly true since R is NPH ?

---

@Arjun sir,

1. all np are decidable, so if Q is reducible to S,Now S is decidable then Q is decidable.C and D can choosen based upon this .Isnt it valid?

2.If S is reducible to R,now S is decidable then we cannot comment on R.

This is what i learnt in TOC.Can you please check where am i wrong?

---

Why is R not in NPC ?

It's given in the question that R is known to be in NP.

Since we know R will be NP-Hard since S is reducible to R, Intersection of NP-Hard & NP is NPC !

---

R is NP-Hard since S which is NPC is reducible to R. R is known to be in NP (Given in the question).

Intersection of NP & NP-Hard is NPC.

Therefore R must be in NPC !

https://en.wikipedia.org/wiki/Euler_diagram 

---

@ms9812
Question says that "Q and R are other two problems NOT known to be in NP".
Therefore, R can not be NPC.

---

Ok. I read the question wrong. But R can be both in NPC or NP-Hard.

So we choose a general answer which is NP-Hard (because NP-Hard includes NPC also).

Question doesn't imply that Q & R are not in NP. If so, Q won't be reducible to S which is NPC !

---

Question clearly states in its first line that Q and R are not known to be in NP. This line itself means that Q and R are not NPC.

---

But if so, how is Q polynomial time reducible to S ?

S is NPC and thus Q has to be P, NP or NPC (all come under NP).

---

It is not necessary for Q to be P, NP or NPC to be able to reduce to an NPC. Nothing can be said about Q with certainity.

---

Why not R can be NP complete?

Answer 2

Q cannot be NP hard as no np hard problems(unless they are np) can be polynomial time reducible to np complete. Answer is B, as npc problem can be reducible to np hard problem. But there is confusion if Q is not NP hard then what complexity class it is in!!

Comments

Q can be in P..

---

the relation given is something like this:

Q <= S <= R        Where S is NPC and Q and R is given unknown..

So R has to be more than or equal to S.. that is it belongs to NPH class  { Note NPC problems also belongs to NPH, but here it's not a guarantee that will lie in NPC boundary so it may lie outside it.. So option (A) is wrong}

Q has to be less than or equal to S.. that means Q is in NP.. { NPC, P also belongs to NP class, offcourse Q can not be NPH so option (D) is wrong}

So we can easily see option (B) is the only correct always.. in option (C) Q can be NPC but is not necessary...

---

@Arjun Sir

P is contained in NP class. So if it's in P it must be in NP as well.

---

obviously yes.

---

Hi, can you please explain if NP complete problem is reducible to another problem in polynomial time, then why it is not NP complete? After all all NP complete problems are NP hard but not all NP hard are NP complete?

---

@Arjun sir, R is polynomial time reducible from S. So can R be NP Complete?

Answer 3

Q is Np hard from the definition ..we cannot say it np complete because we are not sure whether q belongs to np or not

Answer 4

Since S is in NPC and S is reducible to R, R is either NPC or NP-Hard.

So we choose a general answer which is NP-Hard (because NP-Hard includes NPC also).

I think question doesn't imply that Q & R are not in NP. If so, Q won't be reducible to S !

Since Q is reducible to S, Q will be P, NP or NPC (all come under NP).