If X is polynomial reduction to Y and Y is in NP, then X is in NP? [duplicate]

Question

If X is polynomial reduction to Y and Y is in NP, then X is in NP?

Is this true, false or "we don't know"? Why?

Answer 1

It's true:

Assume $Y\in NP$. Now let $N$ be the poly time verifier for $Y$. Lets also call the poly time reduction $\phi$.

Then, notice that $x\in X\iff\phi(x)\in Y\iff \exists w.N(\phi(x),w)$.

Therefore, let us build the poly time verifier for $X$ as follows:

$M(x,w):$

• Compute $\phi(x)$ in poly time
• Emulate $N(\phi(x),w)$ and accept if and only if $N$ accepted.

Now $M$ is polynomial since $\phi$ is and also $N$ is. We also have $x\in X\iff \exists w.N(\phi(x),w)\iff \exists w.M(x,w)$ and thus $M$ is a poly time verifier for $X$, and so we can conclude $X\in NP$