Persamaan linear diophantine dalam bilangan bulat non-negatif

Hanya ada sedikit informasi yang dapat saya temukan pada masalah NP-lengkap untuk menyelesaikan persamaan linear diophantine dalam bilangan bulat non-negatif. Artinya, apakah ada solusi dalam non-negatif dengan persamaan , di mana semua konstanta positif? Satu-satunya penyebutan penting dari masalah ini yang saya ketahui adalah dalam Teori Pemrograman Linear dan Integer milik Schrijver . Dan bahkan kemudian, itu adalah diskusi yang agak singkat. $x_1,x_2, ... , x_n$ $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$

Jadi saya akan sangat menghargai informasi atau referensi yang dapat Anda berikan tentang masalah ini.

Ada dua pertanyaan yang paling saya pedulikan:

Apakah ini NP-Lengkap?
Apakah masalah terkait menghitung jumlah solusi # P-hard, atau bahkan # P-complete?

cc.complexity-theory reference-request np-hardness counting-complexity 4evergr8ful
sumber

Ini benar-benar bukan pertanyaan tingkat penelitian dan saya merasa sulit untuk percaya bahwa Anda tidak menemukan informasi lebih lanjut. Mulai di sini: en.wikipedia.org/wiki/Knapsack_problem

domotorp

untuk 2), afaik tidak ada contoh yang diketahui dari masalah NP-complete yang versi penghitungan alami tidak # P-complete. mencari tahu reduksi pelit untuk masalah khusus Anda mungkin lebih mudah daripada menemukan referensi. makalah ini melakukannya untuk #SubsetSum yang terkait erat: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf

Sasho Nikolov

Bolehkah saya minta sedikit @domotorp dan 4evergr8ful untuk sedikit kesopanan? Yang pertama bisa menjelaskan bagaimana masalah ransel berkurang ke persamaan Diophantine seperti itu, yang menurutnya adalah masalahnya, sementara 4evergr8ful mungkin bisa tenang, terutama karena dia sama-sama meminta bantuan dan jelas tidak berpengalaman dalam kerja forum ini. . Tetapi saya juga memikirkan masalah ransel, dan sama sekali tidak jelas bagi saya bahwa itu mengurangi solusi positif dari persamaan Diophantine.

Andrej Bauer

OP, seperti yang disebutkan @Austin, ide program dinamis yang sama dengan knapsack berfungsi untuk menyelesaikan masalah Anda dalam waktu polinomial ketika

dibatasi polinomial. jadi, tidak, masalahnya tidak terlalu lengkap. dan domotorp punya alasan bagus untuk mengarahkan Anda ke halaman wiki ransel.

a_{i}

$a_i$

Sasho Nikolov

@ 4evergr8ful Tentu, saya berasumsi bahwa Anda memparafrasekan kutipan. Itu tidak apa-apa. Namun, Anda salah mengutip dengan mengubah "enam" menjadi "setiap". Karena G&J mendefinisikan pelit (yaitu jumlah solusi persis sama), TIDAK benar bahwa setiap pengurangan antara masalah dalam NP dapat dibuat pelit. KECUALI P = Paritas-P. Alasan untuk ini adalah bahwa pengurangan standar dari SAT ke NAE-SAT memperkenalkan faktor yang merupakan kekuatan 2. Ini diharapkan, karena SAT lengkap untuk Parity-P tetapi NAE-SAT mudah (ada pasangan yang jelas dari tugas jadi jawabannya selalu genap = 0).

Tyson Williams

Jawaban:

Mengenai (1), masalahnya bukan NP-hard, cf Corollary 1 di sini :

Papadimitriou, CH (1981). Pada kompleksitas pemrograman integer. Jurnal ACM , 28 (4), 765-768.

Mengenai (2), masalahnya jelas terletak pada #P jika semua konstanta positif. Ada juga versi # P-complete dari SubsetSum, yang hampir cocok dengan contoh masalah Anda tetapi, bagaimanapun, mengharuskan menjadi 0 atau 1, lihat di sini : $x_i$

Faliszewski, P. dan Hemaspaandra, L. (2009). Kompleksitas perbandingan indeks daya. Ilmu Komputer Teoritis 410 (1), 101-107.

$x_i\in \{0,1\}$

Christoph Haase
sumber

Saya sama sekali bukan ahli dalam hal ini, tetapi saya ingin memulai diskusi yang konstruktif. Berikut adalah upaya, berdasarkan pertanyaan math.stackexchange.com Hitung jumlah solusi positif untuk persamaan linear diophantine . Hal-hal tersebut terkait dengan polinomial Erhart, yang saya tidak tahu tentangnya, dan saya pikir juga untuk komentar @ SashoNikolov di atas.

$N(a_1, a_2, \ldots, a_n; b)$

a_{n} x_{n} + a_{n - 1} x_{n - 1} + \dots + a_{1} x_{1} = b,

$a_n x_n + a_{n-1} x_{n-1} + \cdots + a_1 x_1 = b,$

a_{i}

$a_i$

b

$b$

N (a_{1}; b) = {\begin{cases} 1 & if a_{1} ∣ b \\ 0 & otherwise \end{cases}

$N(a_1; b) = \begin{cases} 1 & \text{if $a_1 \mid b$} \\\\ 0 & \text{otherwise} \end{cases}$

N (a_{1}, \dots, a_{n + 1}; b) = \sum_{0 \leq k \leq b / a_{n + 1}} N (a_{1}, \dots, a_{n}; b - a_{n + 1} k)

$N(a_1, \ldots, a_{n+1}; b) = \sum_{0 \leq \ k \ \leq b/a_{n+1}} N(a_1, \ldots, a_n; b - a_{n+1} k)$

k

$k$

b

$b$

Andrej Bauer
sumber

Andrej yang terhormat, dalam kasus kekerasan NP yang kuat, kami mengukur dalam hal nilai input dan bukan panjangnya. Lihat juga: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

domotorp

@domotorp, saya pikir Andrej menjawab pertanyaan kedua, tentang # P-kelengkapan, bukan yang pertama tentang kelengkapan-NP yang kuat, yang, sejauh yang saya bisa lihat, sangat mudah dijawab (tidak, masalahnya bukan NP yang kuat) -lengkap). Andrej, saya bingung apa yang ingin Anda tunjukkan di sini? Karena masalah keputusan adalah NP-complete, Anda tidak bisa berharap untuk menghitung jumlah solusi. Apakah Anda berharap dapat memperkirakan jumlah solusi? Atau punya algoritma waktu yang lebih cepat daripada eksponensial?

Sasho Nikolov

BTW, saya pikir kemungkinan bahwa algoritma dalam makalah ini (kira-kira menghitung jumlah solusi untuk knapsack melalui pemrograman dinamis) dapat disesuaikan dengan masalah persamaan diophantine: cs.utexas.edu/ ~klivans

Sasho Nikolov

Saya belajar satu fakta lagi tentang masalah ini. Ada tiga jenis orang: mereka yang menyebutnya masalah #linear diophantine, orang-orang yang menyebutnya masalah ransel # unbound, dan akhirnya mereka yang menyebutnya masalah denumerant. Dan mereka sepertinya tidak berbicara satu sama lain.

4evergr8ful