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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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:
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$