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. 



The NP version of Matiyasevich's theorem
I don’t know about the particular form of the polynomial you are using, but in general, it is a well-known open problem whether every NP set can be represented by a Diophantine equation with a polynomial bound on the length of the solutions. [Adleman and Manders](http://dx.doi.org/10.1016/0022-0000%2878%2990044-2) proved that the set $\{\langle a,b,c\rangle\in\mathbb N^3:(\exists x,y\in\mathbb N)(ax^2+by=c)\}$ is NP-complete, hence the answer is positive iff the class of such representable sets is closed under polynomial-time reductions, but it’s not clear whether the latter is actually true or not. See the introduction of [Pollett](http://www.cs.sjsu.edu/faculty/pollett/papers/hilbert10.ps) for an overview of some known partial results.


