By Matiyasevich, for every recursive set $A$ of natural numbers there exists a polynomial $f(x_1,...,x_n)$ with integer coefficients such that for every $p\ge 0$, $f(x_1,...,x_n)=p$ has integer solutions if and only if $p\in A$.

Now suppose that $A$ is a set of natural numbers with membership problem in $NP$. Is there a polynomial $f$ with integer coefficients such that $f(x_1,...,x_n)=p$ has integer solutions if and only if $p\in A$ and there exists a solution with $||x_i||\le Cp^s$ for some fixed $s, C$, where $||x_i||$ is the length of $x_i$ in binary (i.e. $\sim \log |x_i|$)? Clearly the converse is true: if such a polynomial exists, then the membership problem for $A$ is in NP.

By Matiyasevich, for every recursively enumerable set $A$ of natural numbers there exists a polynomial $f(x_1,...,x_n)$ with integer coefficients such that for every $p\ge 0$, $f(x_1,...,x_n)=p$ has integer solutions if and only if $p\in A$.

Now suppose that $A$ is a set of natural numbers with membership problem in $NP$. Is there a polynomial $f$ with integer coefficients such that $f(x_1,...,x_n)=p$ has integer solutions if and only if $p\in A$ and there exists a solution with $||x_i||\le Cp^s$ for some fixed $s, C$, where $||x_i||$ is the length of $x_i$ in binary (i.e. $\sim \log |x_i|$)? Clearly the converse is true: if such a polynomial exists, then the membership problem for $A$ is in NP.