and isnt it implicitly true since R is NPH ?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

- R is NP-complete
- R is NP-hard
- Q is NP-complete
- Q is NP-hard

+12 votes

Best answer

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

0

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 ?

and isnt it implicitly true since R is NPH ?

0

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

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?

0

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 !

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 !

0

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 !

+1

@ms9812

Question says that "Q and R are other two problems **NOT **known to be in NP".

Therefore, R can not be NPC.

0

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 !

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 !

0

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.

0

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

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

+13 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!!

+6

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

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

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

0 votes

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,748 questions

47,471 answers

145,581 comments

62,234 users