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

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?

• Does this answer your question? If X reduces to a problem in NP, is X in NP? Jul 22 '20 at 13:21
• I’m voting to close this question because it is of low quality. Aug 19 '20 at 8:47

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