Wie kann ich die Teilmengensumme auf Partition reduzieren?

20

Vielleicht ist das ganz einfach, aber ich habe einige Probleme, diese Reduzierung zu bekommen. Ich möchte die Teilmengensumme auf Partition reduzieren, sehe aber derzeit keine Beziehung!

Ist es möglich, dieses Problem mit einer Levin-Reduktion zu reduzieren?

Wenn Sie nicht verstehen, schreiben Sie zur Klarstellung!

Dbonadiman
quelle

Antworten:

19

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=LLS+B,2S-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 .MLBLM{2S-B}LM{S+B}B+(2S-B)=2S(S-B)+(S+B)=2S

(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 BLP1,P2LB(S+B)+(2S-B)=3S2S2SBP1P1LB

Yuval Filmus
quelle
2
Aber das Standard-Teilmengen-Summen-Problem verwendet alle ganzen Zahlen, und das Partitions-Problem verwendet nur nicht negative ganze Zahlen ...
gukoff
SUBSET-SUM ist auch bei nicht-negativen ganzen Zahlen NP-vollständig, zum Beispiel führt die Reduktion von 3SAT zu nicht-negativen ganzen Zahlen. Es gibt wahrscheinlich auch eine direkte Reduzierung von ganzzahligem SUBSET-SUM auf nicht negative ganzzahlige SUBSET-SUM.
Yuval Filmus
1
Ja, ich weiß, und diese Reduzierung ist sehr einfach. Es ist lediglich zu beachten, dass es sich nicht um die Teilmengensumme in der "Standard" -Form handelt. :)
Gukoff
Würde es auch funktionieren, wenn IstL{B,S-B}? als| {B,S-B}| =B, wie| L| =BLL{B,S-B}|{B,S-B}|=B|L|=B
Curious
1
@Issam Wäre es nicht so, hätte die PARTITION-Instanz immer die Lösung . L,{B,S-B}
Yuval Filmus
1

Die von @Yuval Filmus erwähnte Antwort ist falsch (NUR wenn es keine negativen ganzen Zahlen gibt). Betrachten Sie das folgende Multiset:

{-5,2,2,2,2,2}

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 .-22σ-t=12σ+t=3

{5,2,2,2,2,2,3,12}
20

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:

{2,2,2,2,2}

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σ2ttt

Rohit Kumar Jena
quelle
1
Aber, wie Yuval in einem Kommentar zu seiner Antwort sagt, ist die Teilmengensumme NP- vollständig, selbst wenn wir uns auf positive ganze Zahlen beschränken. Wir können also davon ausgehen, dass es keine negativen Zahlen gibt.
David Richerby
1
Ja, ich stimme zu, die Teilmengensumme ist auch bei positiven ganzen Zahlen NP-vollständig. Ich habe nur einen vollständigeren Beweis für eine ganze Zahl geliefert.
Rohit Kumar Jena
1
"Nur einen vollständigeren Beweis erbringen" und zu Unrecht behaupten, dass eine vorhandene Antwort falsch ist.
David Richerby
1
Es ist in dem Sinne falsch, dass es für negative ganze Zahlen nicht funktioniert. :) Frieden :)
Rohit Kumar Jena
1

Hier ist ein klarer Beweis:

Es ist leicht zu erkennen, dass SET-PARTITION in Polynomzeit verifiziert werden kann. Wenn eine Partition P1,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 Menge X und einem Wert t (die Teilmengen-Summenabfrage) eine neue Menge X=X{s2t} wobei s=xXx . Um zu sehen, dass dies eine Reduzierung ist:

  • () nehme an, dass es etwas SX so dass t=xSx dann hätten wir das

    st=xS{s2t}x,
    st=xX(S{s2t})x
    und wir hätten das S{s2t} undX(S{s2t}) bilden eine Partition vonX

  • () Angenommen, es gibt eine Partition P1,P2 von X so dass xP1x=xP2x . Beachten Sie, dass dies eine natürliche Partition P1 und P2 von X induziert, so dass WLOG wir haben, dass

    s-2t+xP1x=xP2x
    s-2t+xP1x+xP1x=xP2x+xP1x=s
    s-2t+2xP1x=s
    xP1x=t

Wir können also aus einer Lösung t=xSx eine Partition P1=S{s-2t} , P2=X(S{s-2t}) und umgekehrt aus einer Partition P1,P2 wir eine Lösung t=xP1{s-2t}xund daher ist die Abbildungf:(X,t)X eine Reduktion (weil(X,t)in der Sprache / Menge SUBSETSUMX=f(X,t)ist) in der Sprache / Menge PARTITION) und es ist klar zu sehen, dass die Transformation in Polynomialzeit erfolgte.

Pedrpan
quelle
0

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

Behrooz Tabesh
quelle
-3

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

user44970
quelle
4
Bitte posten Sie keine Nur-Link-Antworten. Wenn sich der Inhalt des Links ändert oder nicht mehr verfügbar ist, wird Ihre Antwort unbrauchbar. Bitte ändern Sie Ihre Antwort so, dass sie nützlich ist, auch wenn der Link nicht verfügbar ist (z. B. indem Sie den Inhalt in Ihren eigenen Worten neu formulieren und den Link als Referenz und Quelle angeben).
Tom van der Zanden