Reducing to an NP-complete problem

Question

If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$?

I think we should be able to say that $R$ is in NP since an instance of $S$ can have a certificate verified in polynomial time and from the reduction $R \le S$, we could say the same about $R$. Is this reasoning valid? Would it also work if $S$ was only supposed to be in NP rather than NP-complete?

Thanks in advance.

Answer 1

Your reasoning is correct in both cases, modulo an important detail: you need to specify the type of reduction. In this case, I assume you mean many-to-one reductions that are polynomial-time computable, as this is the standard notion of $\textsf{NP}$-completeness. Note that in this case, the ordering is usually written as $\leq_{p}$ or $\leq_{m}^{p}$.

Note that if $S$ is in $\textsf{NP}$ and $R \leq_{m}^{p} S$, then $S$ is an upper-bound for $R$ under the ordering induced by many-to-one polynomial-time computable reductions. Since $R$ is a decision problem, $\leq_{m}^{p}$ is transitive, and $S \in \textsf{NP}$, we have that $R \in \textsf{NP}$. Intuitively, $S$ is a (weakly) better upper bound for $R$ than $\textsf{NP}$.