Sei eine Instanz einer Teilmengen-Summe, wobei eine Liste (Mehrfachmenge) von Zahlen ist und die Zielsumme ist. Lassen . Sei die durch Addition von zu gebildete Liste .L B S = Σ L L ' S + B , 2 S - B L( L , B )LBS= ∑ LL′S+ B , 2 S- BL
(1) Wenn es eine Unterliste , die zu summiert , dann kann in zwei gleiche Teile unterteilt werden: und . In der Tat summiert sich der erste Teil auf und der zweite auf .M⊆ LBL′M∪ { 2 S- B }L ∖ M∪ { S+ B }B + ( 2 S−B)=2S(S−B)+(S+ B ) = 2 S
(2) Wenn in zwei gleiche Teile , gibt es eine Unterliste von , die zu summiert . Da und jeder Teil ergibt, gehören die beiden Elemente zu verschiedenen Teilen. Ohne Einschränkung der Allgemeinheit . Der Rest der Elemente in gehören in und Summe .P 1 , P 2 L B ( S + B ) + ( 2 S - B ) = 3 S 2 S 2 S - B ≤ P 1 P 1 L BL′P1, P2LB( S+ B ) + ( 2 S- B ) = 3 S2 S2 S- B ∈ P1P1LB
Die von @Yuval Filmus erwähnte Antwort ist falsch (NUR wenn es keine negativen ganzen Zahlen gibt). Betrachten Sie das folgende Multiset:
und die Zielsumme ist . Wir wissen, dass es keine Untermenge gibt. Jetzt konstruieren wir die Instanz für das Partitionsproblem. Die beiden neu hinzugefügten Elemente sind 2 σ - t = 12 und σ + t = 3 . Das Multiset ist jetzt: { - 5 , 2 , 2 , 2 , 2 , 2 , 3 , 12 } und die Gesamtsumme ist 20 .−2 2σ−t=12 σ+t=3
Das Partitionsproblem löst die Antwort für die Teilmenge Hier befinden sich die beiden neuen Elemente in derselben Teilmenge (es gibt keine andere Möglichkeit, in die Hälfte der Summe zu partitionieren). Dies ist also ein Gegenbeispiel. Die richtige Antwort lautet wie folgt:
Addiere ein Element, dessen Wert . Die Gesamtsumme des Multisets beträgt nun 2 t . Lösen Sie das Partitionsproblem, das 2 Teilmengen der Summe t ergibt . Nur eine der Partitionen enthält das neue Element. Wir wählen die andere Partition, deren Summe t ist, und wir haben das Teilmengenproblem gelöst, indem wir es in ein Partitionsproblem reduziert haben. Dies ist, was der Link erklärt.2t−σ 2t t t
quelle
Hier ist ein klarer Beweis:
Es ist leicht zu erkennen, dass SET-PARTITION in Polynomzeit verifiziert werden kann. Wenn eine PartitionP1, P2 summieren Sie einfach die beiden und verifizieren, dass ihre Summen einander entsprechen, was offensichtlich eine polynomielle Zeitverifikation ist (da Summation eine polynomielle Operation ist und wir nur höchstens | X| viele Summationen durchführen).
Der Kern des Beweises besteht darin, SUBSETSUM auf PARTITION zu reduzieren; zu diesem Zweck bilden wir bei gegebener MengeX und einem Wert t (die Teilmengen-Summenabfrage) eine neue Menge X′= X∪ { s - 2 t } wobei s = ∑x ∈ Xx . Um zu sehen, dass dies eine Reduzierung ist:
(⟹ ) nehme an, dass es etwas S⊂ X so dass t = ∑x ∈ Sx dann hätten wir das s - t = ∑x ∈ S∪ { s - 2 t }x ,
s - t = ∑x ∈ X′∖ ( S∪ { s - 2 t } )x
und wir hätten das S∪ { s - 2 t } undX′∖ ( S∪ { s - 2 t } ) bilden eine Partition vonX′
(⟸ ) Angenommen, es gibt eine Partition P′1, P′2 von X′ so dass ∑x ∈ P′1x = ∑x ∈ P′2x . Beachten Sie, dass dies eine natürliche Partition P1 und P2 von X induziert, so dass WLOG wir haben, dass s - 2 t + ∑x ∈ P1x = ∑x ∈ P2x
⟹s - 2 t + ∑x ∈ P1x + ∑x ∈ P1x = ∑x ∈ P2x + ∑x ∈ P1x = s
⟹s - 2 t + 2 ∑x ∈ P1x = s
⟹∑x ∈ P1x = t
Wir können also aus einer Lösungt = ∑x ∈ Sx eine Partition P1= S∪ { s - 2 t } , P2= X′∖ ( S∪ { s - 2 t } ) und umgekehrt aus einer Partition P′1, P′2 wir eine Lösung t = ∑x ∈ P′1∖ { s - 2 t }x und daher ist die Abbildungf: ( X, t ) → X′ eine Reduktion (weil( X, T ) in der Sprache / Menge SUBSETSUM⇔ X′= f( X, T ) ist) in der Sprache / Menge PARTITION) und es ist klar zu sehen, dass die Transformation in Polynomialzeit erfolgte.
quelle
Teilmenge Summe:
Eingabe: {a1, a2, ..., am} st M = {1..m} und ai sind nicht negative ganze Zahlen und S⊆ {1..k} und Σai (i∈S) = t
Trennwand:
Eingabe: {a1, a2, ..., am} und S⊆ {1, · · ·, m} st Σai (i∈S) = Σaj (j∉S)
Partition Np Proof: Wenn der Prüfer eine Partition (P1, P2) für den Prüfer bereitstellt, kann der Prüfer auf einfache Weise die Summe von P1 und P2 berechnen und prüfen, ob das Ergebnis in linearer Zeit 0 ist.
NP_Hard: SubsetSum ≤p PARTITION
Sei x die Eingabe von SubsetSum und x = 〈a1, a2, ..., am, t〉 und Σai (i von 1 bis m) = a
Fall 1: 2t> = a:
Sei f (x) = 〈a1, a2, ..., am, am + 1〉 mit am + 1 = 2t − a
Wir wollen zeigen, dass x∈SubsetSum ⇔ f (x) ∈PARTITION ist
es gibt also S⊆ {1, ..., m} st T = {1..m} - S und Σai (i∈T) = at
und sei T '= {1 ... m, m + 1} - S so Σaj (j∈T') = a-t + 2t-a = t
das ist genau Σai (i∈S) = t und es zeigt f (x) ∈PARTITION
Jetzt werden wir auch zeigen, dass f (x) ∈PARTITION ⇔ x⇔SubsetSum
es gibt also S⊆ {1, ..., m, m + 1} st T = {1, ..., m, m + 1} - S und Σai (i∈T) = [a + (2t-a ) -t] = t
und es zeigt Σai (i∈T) = Σaj (j∈S), also m + 1∈T und S⊆ {1, · · ·, m} und Σai (i∈S) = t
also x∈SubsetSum
Fall 2: 2t = <a :
wir können dasselbe überprüfen, aber gerade diesmal ist am + 1 a − 2t
quelle
Dieser Link enthält eine gute Beschreibung der beiden Verringerungen Partition zu Teilmenge-Summe und Teilmenge-Summe zu Partition. Ich denke, es ist offensichtlicher als die Antwort von YUVAL . nützlicher Link
quelle