# The NP version of Matiyasevich's theorem

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.

-
Suppose that, for every instance of p, there was a uniform certificate xbar where the number of components (dimension) of xbar was bounded by a constant. Then it seems to me that the TM that ran the verifier on xbar could be rewritten as your desired polynomial. I do not know how to argue that the certificates have to be uniform in (dimensional) length, although it is clear that the index n is bounded by a polynomial in the bitlength of p. Gerhard "Ask Me About System Design" Paseman, 2011.07.19 –  Gerhard Paseman Jul 20 '11 at 2:54
I should say "every instance p of A". Please forgive this and other typos in the previous comment. Gerhard "Ask Me About System Design" Paseman, 2011.07.19 –  Gerhard Paseman Jul 20 '11 at 2:56
@Gerhard: It cannot be that simple. The conversion from TM to a Diophantine equation is complicated and - at least in Matiyasevich's proof - seems to require exponential slow down. But I may be wrong of course. The proof uses some properties of Pell equations. I wonder if anybody looked at the proof from the complexity point of view. –  Mark Sapir Jul 20 '11 at 3:23
I vaguely recall that someone did look into this from the computational point of view. The results were not great. I'll see if I can dig this up... –  François G. Dorais Jul 20 '11 at 3:49
This question seems seems to have been first posed by Adleman and Manders in 1975, and it is closely connected with unsolved problems in complexity theory; the following paper includes a review of the state of the art in 2003: C. Pollett, On the Bounded Version of Hilbert's Tenth Problem. Archive for Mathematical Logic. Vol. 42. No. 5. 2003. pp. 469--488. You can find a copy on the author's homepage at cs.sjsu.edu/faculty/pollett/papers –  Ali Enayat Jul 20 '11 at 13:47

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.

-
Emil, is it known if they are closed under any smaller complexity class like $\mathsf{NC^0}$? –  Kaveh Jul 20 '11 at 14:03
How do you define uniform $\mathrm{NC}^0$, anyway? As mentioned in Pollett’s paper, all NP-sets are bounded Diophantine if all coNLOGTIME-sets are, so the closure under any class of at least this complexity (which is quite small) is equivalent to the full problem. –  Emil Jeřábek Jul 20 '11 at 14:17
I see. (I didn't pay attention that 𝖣𝖫𝖮𝖦𝖳𝖨𝖬𝖤 uniformity is not good for 𝖭𝖢𝟢.) –  Kaveh Jul 20 '11 at 14:51
@Emil: Thank you! I accept this answer because it came earlier than François' . –  Mark Sapir Jul 20 '11 at 16:20
You are welcome. –  Emil Jeřábek Jul 20 '11 at 16:28

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

-
I had missed Emil's answer while typing this. –  François G. Dorais Jul 20 '11 at 14:37
@François: Thank you! –  Mark Sapir Jul 20 '11 at 16:20
@FrançoisG.Dorais: I know I'm two years late to this thread, but I was hoping to ask you a couple questions. I am very interested in the two NDDM/NDTM time bounds you listed above, and I would like to read the proof, but unfortunately all copies of Diophantine Complexity are behind a paywall. (1) Is the proof of the timebounds given in the DC paper instructive enough to be worth purchase? and (2) are you aware of any other freely available paper that contains these proofs? Thanks so much. –  GMB Jun 27 '13 at 19:22
@LevDub, it's not quite two years but it has been long enough that I don't remember the proofs. I don't have access to the paper right now but I will try to dig it up when I'm back at the office next week. –  François G. Dorais Jun 27 '13 at 21:02