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.

On the Bounded Version of Hilbert's Tenth Problem.Archive for Mathematical Logic. Vol. 42. No. 5. 2003. pp. 469--488. You can find a copy on the author's homepage at cs.sjsu.edu/faculty/pollett/papers $\endgroup$ – Ali Enayat Jul 20 '11 at 13:47