Apakah ada masalah P-lengkap pada persamaan diophantine?

11

Secara umum memutuskan apakah persamaan diophantine memiliki solusi bilangan bulat setara dengan masalah penghentian. Saya percaya bahwa memutuskan apakah persamaan diophantine kuadratik memiliki solusi apa pun adalah NP-complete. Apakah ada batasan lebih lanjut pada persamaan yang terlibat yang menghasilkan masalah P-complete?

cc.complexity-theory linear-algebra polynomials Yakub Edelman
sumber
1
Saya pikir masalah yang berkaitan dengan gcd ditunjukkan P selesai.
T ....
3
@ EmilJeřábek Ups, saya salah menyatakan hasilnya. Solusinya harus dalam rasional positif . Ini terdaftar sebagai masalah A.4.2 dalam Kompendium Masalah Lengkap untuk P , sebuah 1991 Tech. Laporan oleh Greenlaw, dkk.
mhum
2
@ EmilJeřábek Tentu saja melalui bilangan bulat ini hanya pemrograman bilangan bulat. Yang saya maksudkan adalah bahwa membuat pemrograman linier terdengar seperti masalah tipe persamaan diophantine dengan mengatakan Anda menginginkan solusi rasional agak menyesatkan karena bersikeras pada solusi rasional tidak menambah kendala pada masalah. Yaitu jika Anda bertanya apakah sistem persamaan linear memiliki solusi atas real non-negatif masalahnya akan persis sama.
Sasho Nikolov
1
@SashoNikolov Ini bukan kendala. Tanpa menentukan domain untuk solusi, masalahnya hanya buruk , kecuali domain dapat disimpulkan dari konteks. Dan di sini konteksnya sedemikian rupa sehingga domain tersirat akan menjadi bilangan bulat, maka orang perlu secara eksplisit menyatakan itu adalah sesuatu yang berbeda. Ya, di sini tidak masalah apakah seseorang memilih rasional, real, atau bidang karakteristik lainnya 0. Pilihan Mhum untuk menyebutnya "rasional" sama validnya dengan pilihan Anda untuk menyebutnya "nyata".
Emil Jeřábek
1
@ EmilJeřábek Saya sebagian besar setuju dengan apa yang Anda katakan. Apa yang saya gagal sampaikan adalah bahwa bagi saya pemrograman linier tidak memiliki aspek teoretik bilangan dari masalah persamaan diophantine.
Sasho Nikolov

Jawaban:

-3

Tidak, sejauh yang saya tahu masalah diaphantine secara umum tidak dapat dipastikan sehingga setara dengan penghentian masalah, jika persamaan dibatasi menjadi kuadrat maka np-complete, dan persamaan diaphantine linier dapat direduksi menjadi masalah pemrograman bilangan bulat dan Untuk persamaan linear Diophantine persamaan, solusi integral ada jika dan hanya jika, GCD koefisien dari dua variabel membagi istilah konstan dengan sempurna.

riemann77
sumber