Hilbert's tenth problem asks whether there is an algorithm to determine if a given solution set to a Diophantine equation is non-empty. There is no such algorithm.
In practice for many engineering application computer number types such Float64, Float32 (IEEE floating numbers with that many bits) or Int32, Int64. I am interested in polynomial Diophantine equation (with cross terms).
$$x \in A^n; \ w, e \in B^{n \times n \times m}: \forall j \sum_i w_{ij}\prod_k x_k^{e_{ijk}} = 0\text{ where also } e_{ij} \in \mathbb{N}_0$$
It is obvious that if $A \in \{\text{Int32, Int64}\}$ all solutions can be enumerated. Computers can also represent $\mathbb{Z}$ being limited by memory.
| $$A = \mathbb{Z}$$ | $$A \in \{\text{Int32, Int64}\}$$ | |
|---|---|---|
| $$B = \mathbb{Z}$$ | No, see Hilberts 10th problem | completely enumerable |
| $$B \in \{\text{Int32, Int64}\}$$ | b) | completely enumerable |
| $$B \in \{\text{Float32, Float64}\}$$ | c) | completely enumerable |
For b) - any Diophantine equation can be rewritten in form b), even if we require all coefficients and powers to be at most $2$, so b) is at least as hard as Hilbert tenth problem (and obviously not harder, as it's special case of it), so b) can't be solved.
Let the maximal power $e_{ijk}$. Let $u = \lceil\frac{e_{ijk}}{2}\rceil$, $v = \lfloor\frac{e_{ijk}}{2}\rfloor$. Add variables $a, b$ and equations $a - x_k^u = 0$, $b - x_k^v = 0$ and replace $x^{e_{ijk}}$ with $ab$. This either decreases $\max e_{ijk}$ or number of $e_{ijk}$ with maximal value, so after repeating it we can get all powers to be $1$.
The same can be done for coefficients: take $w_{ij}$, add equations $a - \lceil\frac{w_{ij}}{2}\rceil = 0$ and $b - \lceil\frac{w_{ij}}{2}\rceil = 0$ and replace $w_{ij}$ with $a + b$ (increasing number of monomials). Or, if we allow repeating monomials, simply repeat each monomial necessary number of times).
This obviously increases number of variables (as usual, you can replace system $P_i(\vec x) = 0$ with $\sum P_i^2(\vec x) = 0$, so we can rewrite resulting system as single equation if we want, coefficients can go up a bit, but some small constant will still be enough). Of course, if we bound both coefficients and number of variables, we have only finitely many different equations, so such problem can be solved.
After making coefficients small enough so Float32 can represent them exactly, it doesn't matter if we ask about exact solution of solution with $\epsilon$-precision (as long as $\epsilon < 1$), as with integer coefficients and variables any $\epsilon$-solution is exact. So c) is again at least as hard as Hilbert's tenth problem.