Pengurangan dari masalah 3-Partition ke masalah Balanced Partition

13

Masalah 3-Partisi menanyakan apakah satu set bilangan bulat dapat dipartisi menjadi n set tiga bilangan bulat sehingga setiap set berjumlah hingga beberapa bilangan bulat B yang diberikan . Masalah Balanced Partition menanyakan apakah bilangan bulat 2 n dapat dipartisi menjadi dua set kardinalitas yang sama sehingga kedua set memiliki jumlah yang sama. Kedua masalah diketahui sebagai NP-complete. Namun, 3-Partisi sangat lengkap untuk NP. Saya belum melihat dalam literatur setiap pengurangan dari 3-Partition ke Balanced Partition.3nnB2n

Saya mencari pengurangan (sederhana) dari masalah 3-Partition ke Balanced Partition.

Mohammad Al-Turkistany
sumber
Jadi Anda ingin pemetaan dari instance 3-Partisi instance Balanced Partition? ("pengurangan meta" ke arah yang sama akan mencari pemetaan di sisi lain.)
Raphael
Apa itu reduksi meta?
Mohammad Al-Turkistany
2
Saya mencari pengurangan Karp dari masalah 3-Partition menjadi masalah Balanced Partition. Saya harap itu jelas.
Mohammad Al-Turkistany
1
Saya senang dengan reduksi yang kompleks.
Mohammad Al-Turkistany
2
karena ini lemah , Anda mungkin perlu trik yang mirip dengan yang tentang mengurangi 3SAT untuk itu yang akan menggunakan angka dengan banyak bit. Lihat Sipser misalnya. Dan Anda selalu dapat menggabungkan beberapa pengurangan untuk mendapatkan yang Anda inginkan, lihat ini . NP-hard
Kaveh

Jawaban:

1

Ada ribuan masalah NP-lengkap dalam literatur, dan sebagian besar pasangan tidak memiliki reduksi eksplisit. Karena pengurangan polinomial banyak waktu satu kali dilakukan, cukup bagi para peneliti untuk berhenti ketika grafik pengurangan yang dipublikasikan sangat terkait, membuat penelitian kelengkapan NP menjadi kegiatan yang jauh lebih skalabel.

Meskipun saya benar-benar tidak mengerti intinya, saya akan menghibur Anda dengan memberikan pengurangan yang cukup sederhana dari 3-PARTISI menjadi PARTISI YANG BERIMBANGAN, dengan beberapa petunjuk tentang bagaimana bukti kebenaran berjalan.

Biarkan input ke reduksi menjadi , turunan dari 3-PARTISI. Memverifikasi bahwa Σ i [ 3 n ] x i = n B . Biarkan β menjadi angka besar untuk dipilih nanti. Untuk setiap i [ 3 n ] dan setiap j [ n ] , hasilkan dua angka x i β j + β n +x1,,x3n,BZi[3n]xi=nBβi[3n]j[n] Secara intuitif, angka pertama berarti bahwa x i ditugaskan ke j -partisi 3, dan angka kedua berarti sebaliknya. Istilah x i β j digunakan untuk melacak jumlah 3-partisi j . Istilah β n + j digunakan untuk melacak kardinalitas 3-partisi j . The β

xiβj+βn+j+β2n+i+β(i+4)n+jβ(i+4)n+j.
xijxiβjjβn+jj digunakan untuk memastikan bahwa setiap x i diberikan tepat satu kali. The β (β2n+ixi Istilah n + j digunakan untuk memaksa angka-angka ini ke dalam partisi seimbang yang berbeda.β(i+4)n+j

Keluarkan dua angka lagi Angka pertama mengidentifikasi partisi seimbang sebagai "benar", dan yang lainnya, sebagai "salah". The 1 istilah digunakan untuk memaksa angka-angka ini ke dalam partisi yang seimbang yang berbeda. Istilah lain membentuk perbedaan antara jumlah partisi 3 dan jumlah komplemennya dan ukuran partisi 3 dan ukuran komplemennya dan berapa kali x i ditugaskan.

1+j[n]((n2)Bβj+(3n6)βn+j)+i[3n](n2)β2n+i1.
1xi

harus dipilih cukup besar untuk memastikan bahwa “luapan” tidak dapat terjadi.β

Herm
sumber
2
Sulit untuk mengikuti / percaya konstruksi Anda tanpa ide atau bukti yang rumit. Bisakah Anda memberikan setidaknya satu dari keduanya?
Raphael
0

Makalah ini, Partisi Timbang Cepat Sulit, Bahkan di Grid dan Pohon , oleh Andreas Emil Feldmann berisi apa yang Anda inginkan! Semoga berhasil!

Kami akan menyiapkan kerangka kerja umum untuk pengurangan dari 3-PARTISI menjadi kelas grafik yang berbeda. Ini akan dicapai dengan mengidentifikasi beberapa sifat struktural yang harus dipenuhi oleh grafik yang dibuat dari instance 3-PARTITION, untuk menunjukkan kekerasan dari masalah PARTALIONING k- BALANCED ...k

Daniel
sumber
Makalah ini tidak ada hubungannya dengan masalah yang ditanyakan Mohammad. Yang ini adalah tentang mempartisi simpul grafik sehubungan dengan meminimalkan jumlah tepi antara partisi.
domotorp