Pengurangan dari masalah 3-Partition ke masalah Balanced Partition

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.$3n$$n$$B$$2n$

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

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 $x_1, \ldots, x_{3n}, B \in \mathbb Z$$\sum_{i\in[3n]} x_i = nB$$\beta$$i \in [3n]$$j \in [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

$$x_i \beta^j + \beta^{n+j} + \beta^{2n+i} + \beta^{(i+4)n+j}\\ \beta^{(i+4)n+j}.$$ $x_i$$j$$x_i \beta^j$$j$$\beta^{n+j}$$j$ digunakan untuk memastikan bahwa setiap x i diberikan tepat satu kali. The β $\beta^{2n+i}$$x_i$ Istilah n + j digunakan untuk memaksa angka-angka ini ke dalam partisi seimbang yang berbeda.$\beta^{(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 + \sum_{j\in[n]} \Bigl((n-2)B\beta^j + (3n-6)\beta^{n+j}\Bigr) + \sum_{i\in[3n]} (n-2)\beta^{2n+i}\\ 1.$$ $1$$x_i$

harus dipilih cukup besar untuk memastikan bahwa “luapan” tidak dapat terjadi.$\beta$

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$