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.
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.