Równania diofantyczne i klasy złożoności

Liniowa diofantycznego RÓWNANIA (podane liczbami naturalnymi, , czy są liczbami naturalnymi, i y takie, że ax + by + c = 0 ?) To rozpuszczalny w czasie wielomianowym.$a, b, c$$x$$y$$ax + by + c = 0$

QUADRATIC DIOPHANTINE EQUATIONS ( $ax^2 + by + c = 0$ ) są NP-zupełne ( NP-kompletne problemy decyzyjne dla wielomianów kwadratowych ).

Ogólne RÓWNANIA DIOPHANTINY są nierozstrzygalne (twierdzenie Davisa-Putnama-Robinsona-Matiyasevicha).

Czy istnieją inne klasy równań diofantycznych (z ograniczeniem ich argumentów / zmiennych), które wychwytują inne klasy złożoności (w szczególności PSPACE)?

Ten artykuł, Złożoności obliczeniowe równań diofantycznych z parametrami Tunga, potwierdza kompletność co-NP wariantu z parametrami nad liczbami naturalnymi.

Zauważ, że to zależy w dużej mierze od tego, jaki zestaw rozwiązujesz. Na przykład problem NP-zupełny SUBSET-SUM można uznać za LINEAR DIOPHANTNE EQUATION, gdy ograniczysz swoje rozwiązanie do dodatnich liczb całkowitych. Jeśli dopuścisz także rozwiązania negatywne, jest to możliwe do rozwiązania w czasie wielomianowym. Aby uzyskać doskonałą ankietę, zobacz:

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