Reducing a problem X to an np-complete problem Y.

Question

Say I have a problem X that I can reduce to an NP-complete problem Y. Can I assume that problem X is in NP? Can it not be in NP?

Answer 1

By reduction of problem $X$ to problem $Y$, we mean that there is a polynomial-time algorithm $A$ that takes an instance $x$ of $X$ and produces an instance $A(x)$ of $Y$, such that the answer to $A(x)$ is "yes" if and only if the answer to $x$ is "yes". The size of $A(x)$ is at most polynomial in the size of $x$. If $Y$ is NP-complete, it must in particular be in NP, so there is a
nondeterministic polynomial-time verifier for $Y$. Applying this to $A(x)$ gives a nondeterministic polynomial-time verifier for $X$. So yes, $X$ must be in NP.