Hintergrund: Die Exact-3D-Matching Problem ist wie folgt definiert (Die Definition stammt aus Jeffs Vorlesungsnotiz: Vorlesung 29: NP-harte Probleme . Sie können auch Siehe 3-dimensionaler Abgleich ):
Exact-3D- Matching: Bei einer Menge von $ S $ und einer Sammlung von Drei-Elemente-Teilmengen von $ S $, genannt triples , gibt es eine Untersammlung von disjunkten Tripeln, die genau $ S $ abdecken ?
Das Problem 3-Partition ist definiert als (es ist auch von Vorlesung 29: NP-harte Probleme . Sie können auch auf 3-Partitions-Problem verweisen.):
Kann es bei einer Menge $ S $ von $ 3n $ Ganzzahlen in $ n $ disjunkte Teilmengen mit drei Elementen aufgeteilt werden, sodass jede Teilmenge genau dieselbe Summe hat?
Es ist bekannt, dass das Problem 3-Partition durch Reduzieren der NP-vollständigen Exact-3D-Matching Problem. Und die NP-Vollständigkeit des Exact-3D-Matching -Problems wird bewiesen, indem das 3SAT -Problem darauf reduziert wird (beide sind im Buch Computer und Intraktabilität: Ein Leitfaden zur Theorie der NP-Vollständigkeit ).
Problem: Mein Problem ist:
So beweisen Sie die NP-Vollständigkeit der
Exact-3D-MatchingProblem durch Reduzieren des3-Partition-Problems darauf?
Ich habe weder Papiere noch gefunden Vorlesungsnotizen dazu.
Kommentare
- Nachdem ich eine Antwort gepostet hatte, bemerkte ich, dass der Titel nach der umgekehrten Richtung fragt. Sie sollten es ändern (oder die Frage ändern und meine Antwort ignorieren 🙂
- Ups … Es ist mein Fehler. Ihre Antwort ist genau das, wonach ich frage. Die Reduzierung von
Exact-3D-Matchingauf3-Partitionkann in Lehrbüchern leicht gefunden werden (obwohl die Reduzierung selbst nicht einfach ist). Deshalb bitte ich um die umgekehrte Richtung. Ich werde den Titel ändern und Ihre Antwort akzeptieren.
Antwort
Ich denke, diese Reduzierung sollte funktionieren:
Bei einer 3-PARTITION-Instanz: $ n $ Ganzzahlen $ a_1, \ ldots, a_ {3n} $ und eine Zielsumme $ B $; Markieren Sie jede Ganzzahl mit einem eindeutigen Bezeichner $ \ hat {a_i} $; Erstellen Sie dann eine Sammlung von 3-Element-Teilmengen $ C_j = \ {\ hat {a} _ {i_1}, \ hat {a} _ {i_2}, \ hat {a} _ {i_3} \} $, sodass $ a_ {i_1} + a_ {i_2} + a_ {i_3} = B $ und $ i_1 \ neq i_2 \ neq i_3 $ (die Sammlung enthält $ O (n ^ 3) $ Elemente).
Das Original Das 3-PARTITION-Problem hat genau dann eine Lösung, wenn es ein EXACT-3D-MATCHING $ C_ {j_1}, \ ldots, C_ {j_n} $ gibt, das $ S = \ hat {a} _ {1}, \ ldots abdeckt , \ hat {a} _ {3n} $.
Beispiel: $ A = \ {5,4,3,3,3,2,2,1,1 \}, B = 8 $ wir bauen: $ S = \ {5a, 4a, 3a, 3b, 3c, 2a, 2b, 1a, 1b \} $ und die Sammlung von 3-Element-Teilmengen:
C1 = { 5a, 2a, 1a } C2 = { 5a, 2a, 1b } C3 = { 5a, 2b, 1a } C4 = { 5a, 2b, 1b } C5 = { 4a, 3a, 1a } C6 = { 4a, 3a, 1b } C7 = { 4a, 3b, 1a } C8 = { 4a, 3b, 1b } C9 = { 4a, 3c, 1a } C10 = { 4a, 3c, 1b } C11 = { 4a, 2a, 2b } C12 = { 3a, 3b, 2a } C13 = { 3a, 3b, 2b } C14 = { 3a, 3c, 2a } C15 = { 3a, 3c, 2b } C16 = { 3b, 3c, 2a } C17 = { 3b, 3c, 2b } Ein genaues 3D-MATCHING wird gegeben durch:
C1 = { 5a, 2a, 1a } C6 = { 4a, 3a, 1b } C16 = { 3b, 3c, 2b } , das auch eine gültige Lösung für das ursprüngliche 3-PARTITION-Problem eindeutig identifiziert .
Kommentare
- Ja, es funktioniert. Ich konnte nicht jedes $ a_i $ eindeutig markieren. Vielen Dank.