2
$\begingroup$

What is the decidability status of Hilbert's Tenth problem interpreted over interval arithmetic?

In details, let $p\in\mathbb{Q}[x_1,\ldots,x_n]$ be a Diophantine polynomial. The problem is that of deciding whether there exist $n$ intervals $v_1,\ldots,v_n$ with bounds in $\mathbb{N}$ such that $0\in p(v_1,\ldots,v_n)$ (where $p$ is evaluated using standard interval arithmetic).

Is the problem decidable?

$\endgroup$
6
  • 1
    $\begingroup$ Can you edit the question to give the definition of $p(v_1,\dots,v_n)$? Is it $\{p(x_1,\dots,x_n) : x_1 \in v_1, \dots, x_n \in v_n\}$? Or is it the result of formally multiplying and adding intervals as specified by $p$, with the natural definition for multiplication and addition of intervals? These two are not the same. $\endgroup$ – D.W. Feb 9 at 18:42
  • $\begingroup$ It's the second one. I'll try to edit the question! $\endgroup$ – gigabytes Feb 9 at 18:58
  • 1
    $\begingroup$ Surely the following simple algorithm works? Evaluate the polynomial in interval arithmetic wrt the order $\{-\infty\}\cup\mathbb Z\cup\{+\infty\}$ with each $v_i$ given the value $[0,+\infty]$. Accept if the result includes $0$. (The semantics of $+\infty$ here is that if the value of some subpolynomial $f$ is $[a,+\infty]$, it means “for every $b>a$, there is an assignment of finite intervals to $v_1,\dots,v_n$ such that the value of $f$ includes $[a,b]$”, and similarly for $-\infty$.) $\endgroup$ – Emil Jeřábek Feb 9 at 21:23
  • $\begingroup$ I'm not sure I understand your proposal. Can you elaborate? $\endgroup$ – gigabytes Feb 10 at 8:17
  • 2
    $\begingroup$ I’m saying that since interval arithmetic is monotone with respect to inclusion, the problem is decidable by fixing each $v_i$ as the largest interval possible, viz. $[0,+\infty]$, and checking whether the resulting interval $p(v_1,\dots,v_n)$ contains $0$. One can easily show (using continuity of interval arithmetic) that if the answer is positive, $p(v_1,\dots,v_n)$ will also contain $0$ when each $v_i$ is set to any sufficiently large finite interval $[0,b]$, hence the result of the algorithm is valid even if you only allow finite intervals for $v_1,\dots,v_n$. $\endgroup$ – Emil Jeřábek Feb 10 at 13:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.