32
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 20, 2011 at 2:54
  • 5
    $\begingroup$ @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. $\endgroup$
    – user6976
    Commented Jul 20, 2011 at 3:23
  • 1
    $\begingroup$ 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... $\endgroup$
    – François G. Dorais
    Commented Jul 20, 2011 at 3:49
  • 5
    $\begingroup$ 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 $\endgroup$
    – Ali Enayat
    Commented Jul 20, 2011 at 13:47
  • 1
    $\begingroup$ The Adleman and Manders paper was the answer to a related question I asked awhile back: mathoverflow.net/questions/36420/… $\endgroup$
    – R Hahn
    Commented Jul 20, 2011 at 23:30

2 Answers 2

Reset to default
21
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Emil, is it known if they are closed under any smaller complexity class like $\mathsf{NC^0}$? $\endgroup$
    – Kaveh
    Commented Jul 20, 2011 at 14:03
  • 2
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Jul 20, 2011 at 14:17
  • $\begingroup$ I see. (I didn't pay attention that 𝖣𝖫𝖮𝖦𝖳𝖨𝖬𝖤 uniformity is not good for 𝖭𝖢𝟢.) $\endgroup$
    – Kaveh
    Commented Jul 20, 2011 at 14:51
16
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I had missed Emil's answer while typing this. $\endgroup$
    – François G. Dorais
    Commented Jul 20, 2011 at 14:37
  • $\begingroup$ @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. $\endgroup$
    – GMB
    Commented Jun 27, 2013 at 19:22
  • 1
    $\begingroup$ @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. $\endgroup$
    – François G. Dorais
    Commented Jun 27, 2013 at 21:02

You must log in to answer this question.