When is the complement of a diophantine set in the naturals also diophantine? A diophantine polynomial is a (multivariable) polynomial with integer coefficients.  If we write this polynomial as $p(x, y_1, \dots, y_n)$, then it defines the diophantine set $D_p = \{ x \in \mathbb{N} \, | \, \exists y_1, \dots, y_n \in \mathbb{Z} \text{ such that } p(x, y_1, \dots, y_n) = 0 \}$.  Is it possible to mathematically characterize the polynomials $p$ for which $\mathbb{N} \setminus D_p$ is also generated by some diophantine polynomial $q$?  If so, to what extent is it possible to express $q$ in terms of $p$?
My motivation for this question is Matiyasevich's Theorem, which says that the Turing-recognizable sets are precisely the diophantine sets.  I wonder if anything similar can be said about the Turing-decidable sets.
 A: It is well-known that the Diophantine sets are precisely the r.e. sets. We show that in general we cannot construct a $q$ given $p$. 
Suppose that we could. Let $A$ be an r.e. set which is not recursive. From $A$, we can construct a polynomial $p(x,y_1,\dots,y_n)$ that represents $A$. 
Suppose that we could construct a $q$ as described in the post. Then we could, given $x$, set one computer to search systematically for a solution $(y_1,\dots,y_n)$ of $p(x,y_1,\dots,y_n)=0$. Simultaneously, another computer can search for a solution of $q(x,z_1,\dots, z_m)=0$. 
This combination algorithm always terminates, contradicting the fact that $A$ is not recursive.
A: A $q$ exists if and only if $p$ (and therefore $q$) defines a recursive set.
There is no terminating algorithm to generate $q$ from $p$ whenever possible, and stop otherwise.   That would be a way to algorithmically test recursiveness of the solution set of a Diophantine equation, which is the same as automated recursiveness testing of the language accepted by a Turing machine.
It is conceivable that if recursiveness is proved in a constructive formal system (one where existence proofs have extractible algorithms for producing witnesses), you get a construction of $q$ from a construction of $p$, but I am not certain of this and it might depend on how recursiveness is defined. 
