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:
- If A is accepted on a NDDM within time $T$, then A is accepted on a NDTM within time $T^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 R0 is the problem of determining whether all even bits of a natural number are zero, then R0 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.