The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

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

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 ?

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

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 !

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

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 835
- Others 1.2k
- Admissions 263
- Exam Queries 390
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 6

33,593 questions

40,128 answers

114,021 comments

38,389 users