Ecuaciones diofantinas y clases de complejidad.

ECUACIONES LINEALES DE DIOPHANTINE (dados los números naturales , ¿hay números naturales e tales que ?) Se puedan resolver en tiempo polinómico.$a, b, c$$x$$y$$ax + by + c = 0$

Las ECUACIONES DE DIOFANTINA CUADRÁTICA ( ) son NP completas ( problemas de decisión NP completos para polinomios cuadráticos ).$ax^2 + by + c = 0$

Las ecuaciones generales de DIOPHANTINE son indecidibles (teorema de Davis-Putnam-Robinson-Matiyasevich).

¿Existen otras clases de ecuaciones de diofantina (con restricciones en sus argumentos / variables) que capturan otras clases de complejidad (en particular PSPACE)?

Este artículo, Complejidades computacionales de las ecuaciones de diofantina con parámetros de Tung, demuestra la completitud de co-NP de una variante con parámetros sobre números naturales.

Tenga en cuenta que depende mucho de qué conjunto está resolviendo. Por ejemplo, el problema NP-complete SUBSET-SUM puede considerarse como una ECUACIÓN DE DIOPHANTNE LINEAL, cuando restringe su solución a enteros positivos. Si permite también soluciones negativas, entonces es solucionable en tiempo polinómico. Para una excelente encuesta, ver:

[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.3864[[1]