<p>What is the decidability status of Hilbert's Tenth problem interpreted over <a href="https://en.wikipedia.org/wiki/Interval_arithmetic" rel="nofollow noreferrer">interval arithmetic</a>?</p>
<p>In details, let <span class="math-container">$p\in\mathbb{Q}[x_1,\ldots,x_n]$</span> be a Diophantine polynomial. The problem is that of deciding whether there exist <span class="math-container">$n$</span> intervals <span class="math-container">$v_1,\ldots,v_n$</span> with bounds in <span class="math-container">$\mathbb{N}$</span> such that <span class="math-container">$0\in p(v_1,\ldots,v_n)$</span> (where <span class="math-container">$p$</span> is evaluated using standard interval arithmetic).</p>
<p>Is the problem decidable?</p>

CC BY-SA 4.0
2021-02-09T18:42:22.493Z
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.
D.W.
CC BY-SA 4.0
2021-02-09T18:58:04.797Z
It's the second one. I'll try to edit the question!
Nicola Gigante
CC BY-SA 4.0
2021-02-09T21:23:42.573Z
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$.)
Emil Jeřábek
CC BY-SA 4.0
2021-02-10T08:17:07.587Z
I'm not sure I understand your proposal. Can you elaborate?
Nicola Gigante
CC BY-SA 4.0
2021-02-10T13:44:41.997Z
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$.
Emil Jeřábek
CC BY-SA 4.0
2021-02-10T15:28:21.757Z
Hm yes, that seems to work, thank you! And the problem seems computationally very easy as well.
Nicola Gigante
<decidability>
Tenth Hilbert problem on interval arithmetic
Nicola Gigante
# Tenth Hilbert problem on interval arithmetic

(Asked by: username_0 on 2021-02-09)

What is the decidability status of Hilbert's Tenth problem interpreted over [interval arithmetic](https://en.wikipedia.org/wiki/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?

**Tags:** decidability
> **Comments:**
> **username_1**: 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.  
> **username_0**: It's the second one. I'll try to edit the question!  
> **username_2**: 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$.)  
> **username_0**: I'm not sure I understand your proposal. Can you elaborate?  
> **username_2**: 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$.  
> **username_0**: Hm yes, that seems to work, thank you! And the problem seems computationally very easy as well.  

---

## 0 answers

