polynomial reduction within Np

Question

If $A \le_p B$ and $B\in NP$, does it necessarily follow that $A\in NP$?
($\le_p$ is a polynomial many-one reduction)

A quick yes/no comment is enough, a proof would be nice :-)

Answer 1

Yes: we know that being in $NP$ is equivalent to having a polynomial verifier.

Let $M$ be the verifier of $B$ (getting an input $x$ and a witness $w$), and let $f$ be the reduction function.

Then, define $M'(x,w):=M(f(x), w)$. Since $x\in A\iff f(x)\in B$, then $\exists w. M(f(x),w) \iff f(x)\in B\iff x\in A$, and thus $M'$ is a verifier for $A$, hence $A\in NP$