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

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?

  1. R is NP-complete
  2. R is NP-hard
  3. Q is NP-complete
  4. Q is NP-hard
asked in Algorithms by Loyal (4.3k points)
edited by | 1.7k views

3 Answers

+5 votes
Best answer

Answer B.

As S is NPC i.e NPHard and NP.

We know that If NPHard problem is reducable to another problem in Polynomial Time, then that problem is also NPHard which means every NP problem can be reduced to this problem in Polynomial Time

Therefore R is NPHard.

Now Q is reduced To S in polynomial time. 

If Q is reducable 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.

answered by Active (1.7k points)
edited by
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 ! 

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

+12 votes
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!!
answered by Boss (7k points)
edited by
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?
0 votes
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
answered by Veteran (14.3k points)

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

33,593 questions
40,128 answers
38,389 users