Persamaan diophantine dan kelas kompleksitas

PERSAMAAN LINEAR DIOPHANTINE (diberikan bilangan asli , adakah bilangan asli dan sedemikian sehingga ?) Dapat dipecahkan dalam waktu polinomial.$a, b, c$$x$$y$$ax + by + c = 0$

PERSAMAAN DIOPHANTIN KUADRATIK ( ) adalah NP-complete ( masalah keputusan NP-lengkap untuk polinomial kuadrat ).$ax^2 + by + c = 0$

PERSAMAAN DIOPHANTINIUM umum tidak dapat dipastikan (teorema Davis-Putnam-Robinson-Matiyasevich).

Apakah ada kelas lain dari persamaan Diophantine (dengan pembatasan argumen / variabelnya) yang menangkap kelas kompleksitas lainnya (khususnya PSPACE)?

Makalah ini, kompleksitas komputasi dari persamaan Diophantine dengan parameter oleh Tung, membuktikan kelengkapan co-NP dari varian dengan parameter lebih dari bilangan asli.

Perhatikan bahwa itu sangat tergantung pada set apa yang Anda selesaikan. Misalnya, masalah SUBSET-SUM NP-lengkap dapat dianggap sebagai LINEAR DIOPHANTNE EQUATION, ketika Anda membatasi solusi Anda di atas bilangan bulat positif. Jika Anda mengizinkan juga solusi negatif maka ini dapat dipecahkan dalam waktu polinomial. Untuk survei yang sangat baik, lihat:

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