MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## 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 2011 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 2011 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 2011 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 2011 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 2011 at 13:47
show 1 more comment

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 2011 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 2011 at 14:17
I see. (I didn't pay attention that 𝖣𝖫𝖮𝖦𝖳𝖨𝖬𝖤 uniformity is not good for 𝖭𝖢𝟢.) – Kaveh Jul 20 2011 at 14:51
@Emil: Thank you! I accept this answer because it came earlier than François' . – Mark Sapir Jul 20 2011 at 16:20
You are welcome. – Emil Jeřábek Jul 20 2011 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 2011 at 14:37 @François: Thank you! – Mark Sapir Jul 20 2011 at 16:20