edited by
17,825 views
21 votes
21 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
edited by

5 Answers

Best answer
20 votes
20 votes

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

edited by
15 votes
15 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!!
edited by
2 votes
2 votes
For anyone having troubles with this concept, read this as the golden rule.

We reduce problems to equivalently hard, or harder problems; so that the solution of the problem in hand, can be used to solve the harder problem.

Given: S is NPC.

Q → S, means Q is easier than S. Or, S is harder than Q. There's no rockbottom here. Q could be easy as heck, or almost as hard. Q could be NP, P, CFL, RL — anything. Can't conclude.

S → R, means R is harder than S. Here, we have a rockbottom. R is NP, because S is NP. R could be more than NP, but we know for a fact that it is at least NP.

Now, is it strictly NP, or undecidable, or not partially decidable, we don't know.

Hence, R is NPH (Because we know NP, but don't know if strictly in NP)
1 votes
1 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).

Answer:

Related questions

15 votes
15 votes
7 answers
4
Kathleen asked Sep 18, 2014
11,658 views
The problem $\text{3-SAT}$ and $\text{2-SAT}$ are both in $\text{P}$both $\text{NP}$ complete$\text{NP}$-complete and in $\text{P}$ respectivelyundecidable and $\text{NP}...