Bagaimana saya bisa mengurangi Jumlah Subset ke Partisi?

Mungkin ini cukup sederhana tetapi saya memiliki beberapa kesulitan untuk mendapatkan pengurangan ini. Saya ingin mengurangi Jumlah Subset ke Partisi tetapi saat ini saya tidak melihat hubungannya!

Apakah mungkin untuk mengurangi masalah ini menggunakan Pengurangan Levin?

Jika Anda tidak mengerti menulis untuk klarifikasi!

Misalkan $(L,B)$ adalah turunan dari jumlah subset, di mana $L$ adalah daftar (multiset) angka, dan $B$ adalah jumlah target. Biarkan $S = \sum L$ . Biarkan $L'$ menjadi daftar yang dibentuk dengan menambahkan $S+B,2S-B$ ke $L$ .

(1) Jika ada sublist $M \subseteq L$ penjumlahan ke $B$ , maka $L'$ dapat dipartisi menjadi dua bagian yang sama: $M \cup \{ 2S-B \}$ dan $L\setminus M \cup \{ S+B \}$ . Memang, bagian pertama berjumlah $B+(2S-B) = 2S$ , dan yang kedua ke $(S-B)+(S+B) = 2S$ .

(2) Jika $L'$ dapat dibagi menjadi dua bagian yang sama $P_1,P_2$ , maka ada subdaftar $L$ menjumlahkan untuk $B$ . Memang, karena $(S+B)+(2S-B) = 3S$ dan masing-masing bagian berjumlah $2S$ , kedua elemen tersebut memiliki bagian yang berbeda. Tanpa kehilangan sifat umum, $2S-B \in P_1$ . Sisa elemen dalam $P_1$ termasuk dalam$L$ dan jumlah untuk$B$ .

Jawaban yang disebutkan oleh @Yuval Filmus salah (HANYA benar jika tidak ada bilangan bulat negatif). Pertimbangkan multiset berikut:

dan jumlah targetnya adalah . Kita tahu bahwa tidak ada himpunan bagian. Sekarang, kami membuat instance untuk masalah partisi. Dua elemen baru yang ditambahkan adalah 2 σ - t = 12 dan σ + t = 3 . Multiset sekarang: { - 5 , 2 , 2 , 2 , 2 , 2 , 3 , 12 } dan jumlah totalnya adalah $-2$$2\sigma-t = 12$$\sigma+t = 3$

Masalah partisi memecahkan jawaban memberikan subset Di sini, 2 elemen baru berada di subset yang sama (tidak ada cara lain untuk mempartisi menjadi setengah jumlah). Karenanya, ini adalah contoh balasan. Jawaban yang benar adalah sebagai berikut:

Tambahkan elemen yang nilainya . Jumlah total multiset sekarang 2 t . Selesaikan masalah partisi yang akan memberikan 2 himpunan bagian dari jumlah t . Hanya satu partisi yang akan mengandung elemen baru. Kami memilih partisi lain yang jumlahnya t dan kami telah memecahkan masalah subset dengan menguranginya menjadi masalah partisi. Inilah yang dijelaskan tautan .$2t-\sigma$$2t$$t$$t$

Berikut ini adalah bukti langsung:

Sangat mudah untuk melihat bahwa SET-PARTITION dapat diverifikasi dalam waktu polinomial; diberi partisi $P_1,P_2$ hanya menjumlahkan keduanya dan memverifikasi bahwa jumlah mereka sama satu sama lain, yang jelas merupakan verifikasi waktu polinomial (karena penjumlahan adalah operasi polinomial dan kami hanya melakukan paling banyak $|X|$ banyak penjumlahan).

Inti dari buktinya adalah dalam mengurangi SUBSETSUM menjadi PARTISI; untuk itu diberikan himpunan $X$ dan nilai $t$ (kueri jumlah himpunan bagian) kami membentuk himpunan $X'=X \cup \{s-2t\}$ di mana$s=\sum_{x \in X}x$ . Untuk melihat bahwa ini adalah pengurangan:

• ($\implies$) Menganggap terdapat beberapa $S \subset X$ sehingga $t=\sum_{x \in S}x$ maka kita akan memiliki bahwa

  $$\begin{equation*} s-t=\sum_{x \in S\cup \{ s-2t \} }x, \end{equation*}$$ $$\begin{equation*} s-t=\sum_{x \in X' \setminus( S\cup \{s-2t\})}x \end{equation*}$$ dan kita akan memiliki$S\cup \{ s-2t \}$ dan$X' \setminus( S\cup \{s-2t\})$ membentuk partisi$X'$

• ($\impliedby$) Misalkan ada partisi $P_1',P_2'$ dari $X'$ sehingga $\sum_{x \in P_1'}x= \sum_{x \in P_2'}x$ . Perhatikan bahwa menginduksi ini partisi alami $P_1$ dan $P_2$ dari $X$ sehingga WLOG kita memiliki

  $$\begin{equation*} s-2t+\sum_{x \in P_1}x= \sum_{x \in P_2}x \end{equation*}$$ $$\begin{equation*} \implies s-2t+\sum_{x \in P_1}x+\sum_{x \in P_1}x= \sum_{x \in P_2}x+\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies s-2t+2\sum_{x \in P_1}x = s \end{equation*}$$ $$\begin{equation*} \implies \sum_{x \in P_1}x = t \end{equation*}$$

Maka dari solusi $t=\sum_{x \in S}x$ kita dapat membentuk parition $P_1 =S\cup \{ s-2t \}$ , $P_2=X' \setminus( S\cup \{s-2t\})$ dan sebaliknya dari partisi $P_1',P_2'$ kita dapat membentuk soltuion $t=\sum_{x \in P_1'\setminus \{s-2t\}}x$dan karenanya pemetaan$f:(X,t)\rightarrow X'$ adalah pengurangan (karena$(X,t)$ adalah dalam bahasa / himpunan SUBSETSUM$\Leftrightarrow X'=f(X,t)$ adalah dalam bahasa / set PARTISI) dan jelas untuk melihat bahwa transformasi dilakukan dalam waktu polinomial.

Jumlah Subset:

Input: {a1, a2, ..., am} st M = {1..m} dan ai adalah bilangan bulat tidak negatif dan S⊆ {1..k} dan Σai (i∈S) = t

Partisi:

Input: {a1, a2, ..., am} dan S⊆ {1, · · ·, m} st Σai (i∈S) = Σaj (j∉S)

Partition Np Proof: jika prover menyediakan partisi (P1, P2) untuk verifier, verifier dapat dengan mudah menghitung jumlah P1 dan P2 dan memeriksa apakah hasilnya 0 dalam waktu linier.

NP_Hard: SubsetSum ≤p PARTITION

Biarkan x menjadi input dari SubsetSum dan x = 〈a1, a2, ..., am, t〉 dan Σai (i dari 1 hingga m) = a

Case1: 2t> = a:

Biarkan f (x) = 〈a1, a2, ..., am, am + 1〉 di mana + 1 = 2t − a

Kami ingin menunjukkan bahwa xSubsetSum ⇔ f (x) ∈PARTISI

jadi ada S⊆ {1, ..., m} st T = {1..m} - S dan Σai (i∈T) = at

dan Biarkan T '= {1 ... m, m + 1} - S so Σaj (j∈T') = a-t + 2t-a = t

yang persis Σai (i∈S) = t dan itu menunjukkan f (x) ∈PARTISI

sekarang Kami juga akan menunjukkan itu f (x) ARTPARTISI ⇔ x∈SubsetSum

jadi ada S⊆ {1, ..., m, m + 1} st T = {1, ..., m, m + 1} - S dan Σai (i∈T) = [a + (2t-a ) -t] = t

dan ini menunjukkan Σai (i∈T) = Σaj (j∈S) jadi m + 1∈T dan S⊆ {1, · · ·, m} dan Σai (i∈S) = t

jadi x∈SubsetSum

Kasus 2: 2t = <a :

kita bisa mengecek sama tetapi kali ini +1 adalah − 2t

tautan ini memiliki deskripsi yang baik tentang reduksi, partisi ke subset-sum dan subset-sum ke partisi. Saya pikir ini lebih jelas daripada jawaban YUVAL . tautan bermanfaat