Siguiente: Procedimiento de reducción de Un nivel arriba: Ecuaciones diofantinas en general Anterior: .

.

Dado que existen conjuntos r.e. que no son recursivos tenemos que no se puede tener procedimiento computable para decidir cuándo una ecuación diofantina posee solución en los enteros, es decir, el Décimo Problema de Hilbert es irresoluble. Refinamientos del Teorema de Matijacewicz muestran que NO se peuede decidir efectivamnete la existencia de soluciones enteras para polinomios de al menos 9 variables. Entre 3 y 8 variables no se tiene decidida la cuestión de solubilidad efectiva de ecuaciones diofantinas. Con 2 variables, se tiene para el caso lineal que

$$aX_1+bX_2-c=0\mbox{\rm posee soluci\'on entera }\;\Leftrightarrow\;\mbox{\rm m.c.d.}(a,b)\vert c,$$

y, para el caso cubico que si f(X₁,X₂) es un polinomio homogéneo de grado 3 entonces la solubilidad en los enteros de la ecuación

f(X₁,X₂)=0

es decidible mediante un algoritmo exponencial. Para grado 2, veremos que el decidir la solubilidad en los enteros de la ecuación

aX₁²+bX₂-c=0

es un problema completo-NP.