Kompleksitas komputasi dari masalah 3-partisi dengan angka yang berbeda

Pertanyaan ini terkait dengan jawaban yang saya posting sebagai tanggapan terhadap pertanyaan lain.

Masalah 3-partisi adalah masalah berikut:
Instance : Positif bilangan bulat a ₁ , ..., sebuah _n , di mana n = 3m dan jumlah dari n bilangan bulat sama dengan mB, sehingga masing-masing _i memenuhi B / 4 <a _i <B / 2.
Pertanyaan : Bisakah bilangan bulat a ₁ ,…, a _n dipartisi menjadi m multiset sehingga jumlah masing-masing multiset sama dengan B?

Sudah diketahui bahwa masalah 3-partisi adalah NP-complete dalam arti kuat bahwa itu tetap NP-complete bahkan jika angka-angka dalam input diberikan secara unary. Lihat Garey dan Johnson untuk bukti.

Pertanyaan : Apakah masalah 3-partisi tetap NP-lengkap jika angka ₁ , ..., _dan semuanya berbeda? Apakah ini tetap NP-lengkap dalam arti kuat?

(Perasaan saya adalah bahwa jawaban untuk kedua pertanyaan itu mungkin ya karena saya tidak melihat alasan mengapa masalahnya menjadi lebih mudah jika semua angka berbeda.)

Tampaknya tidak ada bukti di Garey dan Johnson yang menetapkan kelengkapan NP versi terbatas ini.

Dalam jawaban untuk pertanyaan lain yang dikaitkan di atas, saya memberikan bukti bahwa masalah 6-partisi (didefinisikan secara analog) dengan angka yang berbeda adalah NP-lengkap dalam arti kuat.

cc.complexity-theory np-hardness Tsuyoshi Ito
sumber

Saya pikir ini adalah masalah penting; Saya menemukan beberapa makalah dalam literatur yang menyatakan atau berasumsi bahwa versi yang ditetapkan sulit, tanpa pembenaran yang lebih baik daripada kutipan ke versi multiset di Garey dan Johnson, dan yang menggunakan asumsi itu dalam klaim kelengkapan NP untuk beberapa masalah lain. .

David Eppstein

Jawaban:

Terbukti pada [1, Corollary 7], bahwa 3-partisi adalah NP-hard ketika integer semuanya berbeda. Batas tidak dikenakan [1], namun hal tersebut tidak membuat perbedaan. $a_1, \ldots, a_n$ $B/4 < a_i < B/2$

[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Realisasi multigraf dari urutan derajat: Maksimalisasi itu mudah, minimisasi itu sulit. Oper. Res. Lett. 36 (5): 594-596 (2008). DOI

Serge Gaspers
sumber

Memaksakan batas mudah dilakukan dengan menambahkan angka besar yang sama ke semua .

B / 4 < a_{i} < B / 2

$B/4 < a_i < B/2$

a_{i}

$a_i$

David Eppstein

Memang, mudah juga untuk memaksakan batas-batas ini.

Serge Gaspers

Terima kasih, itu menjawab pertanyaan saya sepenuhnya. Perhatikan bahwa sebagian masalah penyelesaian persegi Latin dapat dengan mudah diformulasikan sebagai kasus khusus dari pencocokan 3 dimensi. Tidak terpikir oleh saya untuk mengganti 3DM dengan PLSC, tetapi setelah melihat buktinya, pendekatannya tampak sangat alami.

Tsuyoshi Ito