Question

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.

Answer 1

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 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 for an overview of some known partial results.

Answer 2

I think this is still an open problem. The idea of a Non-Deterministic Diophantine Machine (NDDM) was introduced by Adleman and Manders. In their paper Diophantine Complexity, they conjecture that the class of problems recognizable in polynomial time by a NDDM are precisely the problems in NP. However, they only prove the following:

1. If A is accepted on a NDDM within time $T$, then A is accepted on a NDTM within time $T^2$.
2. If A is accepted on a NDTM within time $T$, then A is accepted on a NDDM within time $2^{10T^2}$.

They also show that if R₀ is the problem of determining whether all even bits of a natural number are zero, then R₀ is recognized in polynomial time by a NDDM if and only if all NP problems are recognized in polynomial time by a NDDM.

PS: Technically speaking, a NDDM is not exactly of the type you ask for in your question. However, one recovers the form you desire using Putnam's trick: the equations $P(x,x_1,\ldots,x_n) = 0$ and $x = x(1 - P(x,x_1,\ldots,x_n)^2)$ have exactly the same solutions.