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?
As $S$ is $NPC$ i.e $NP$-$Hard$ and $NP$.
Therefore, $R$ is $NP$-$Hard$.
Now $Q$ is reduced to $S$ in polynomial time.
So, nothing can be concluded about $Q$.
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.
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.
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).
There is one more problem. Ppl who have...