Equações diofantinas e classes de complexidade

EQUAÇÕES DIOFANTINAS LINEARES (dados os números naturais , existem números naturais e tais que ?) São solucionáveis ​​no tempo polinomial.$a, b, c$$x$$y$$ax + by + c = 0$

EQUAÇÕES DIOFANTINAS QUADRÁTICAS ( ) são NP-completas ( problemas de decisão de NP-completas para polinômios quadráticos ).$ax^2 + by + c = 0$

As EQUAÇÕES DIOFANTINAS gerais são indecidíveis (teorema de Davis-Putnam-Robinson-Matiyasevich).

Existem outras classes de equações diofantinas (com restrições em seus argumentos / variáveis) que capturam outras classes de complexidade (em particular PSPACE)?

Este artigo, Complexidades computacionais de equações diofantinas com parâmetros de Tung, comprova a co-NP-completude de uma variante com parâmetros sobre números naturais.

Observe que depende muito de qual conjunto você está resolvendo. Por exemplo, o problema NP completo SUBSET-SUM pode ser considerado uma EQUAÇÃO LINEAR DE DIOFANTAS, quando você restringe sua solução a números inteiros positivos. Se você permitir também soluções negativas, é possível resolver em tempo polinomial. Para uma excelente pesquisa, consulte:

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