Zeigen Sie, dass das Teilmengen-Summenproblem (Gegeben eine Folge von ganzen Zahlen und eine ganze Zahl Gibt es eine Folge von das summiert sich genau ?) ist NP-vollständig.
Hinweis: Verwenden Sie das genaue Deckungsproblem.
Das genaue Deckungsproblem ist das folgende: Bei einer Familie von Sets Gibt es eine Mengenabdeckung, die aus einer Unterfamilie paarweise disjunkter Mengen besteht?
Zunächst einmal, um zu zeigen, dass dieses Problem vorliegt Müssen wir Folgendes tun?
Eine nichtdeterministische Turing-Maschine kann zuerst erraten, nach welcher Subsequenz wir suchen, und dann überprüfen, ob sie in linearer Zeit genau k summiert. Ist das richtig?
Um zu zeigen, dass es NP-vollständig ist, wie können wir das genaue Deckungsproblem auf eine Teilmenge reduzieren? Ist es wie folgt?
Das genaue Deckungsproblem hat eine Lösung, wenn sich jedes Element in genau einem Satz befindet.
Wir betrachten das Set und die Nummer so dass jede Zahl einer Menge von Elementen und entspricht entspricht dem gesamten Satz. Angenommen, es gibt Elemente und verschiedene Sätze.
Wir ersetzen jeden Satz S durch eine Zahl, die ist in seiner i-ten Position, wenn ich in S bin und a hat in seiner i-ten Position anders.
Wir setzen k auf eine Zahl, die ist Kopien der Nummer .
quelle
Antworten:
Grundidee : Im genauen Deckungsproblem wird jedes Element auf eine Zahl reduziert. Dann wird jeder Satz auf die Summe der Zahlen reduziert, die er abdeckt. Zum Schluss setzenk die Summe aller Zahlen sein.
Diese Reduzierung funktioniert immer in eine Richtung: Wenn eine Lösung für das genaue Deckungsproblem existiert, gibt es auch eine Lösung für das Teilmengen-Summenproblem.
Der schwierige Teil ist, den anderen Weg zu beweisen. Trivialzahlen funktionieren nicht. Angenommen, die Elemente sind auf reduziert1,2,3,4 und die Sätze sind
Die Reduktion auf die Teilmengen-Summe sind die Zahlen7,3 und k=10 , die JA zurückgeben, aber es gibt keine Lösung für das genaue Deckungsproblem!
Wir müssen bei der Auswahl der Zahlen klüger sein. Der Fehler in den vorherigen Zahlen ist der folgende3 kann ersetzen 1 , 2 . Wir möchten nicht, dass eine Nummer ersetzt wird. Daher möchten wir, dass die Zahlen ausreichend große Lücken aufweisen. Angenommen, in einem genauen Deckungsproblem vonn Elemente wird das erste Element auf reduziert 1 . Wie groß sollte die zweite Zahl sein? Es gibt2n - 1 Sätze, die die erste Nummer enthalten können. Das zweite Element sollte also auf eine Zahl reduziert werden, die größer als ist2n - 1 so dass egal wie oft 1 erscheint, kann es die zweite Nummer nicht ersetzen. Reduzieren wir einfach das zweite Element auf2n . Das gleiche Argument gilt für das dritte Argument, daher reduzieren wir es auf2n×2n=4n .
Abschließend dieich -th Element im genauen Deckungsproblem hat einen Wert von 2i n . Jeder Satz wird auf die Summe der Zahlen reduziert, die er abdeckt.
Jetzt haben wir gezeigt, dass die genaue Abdeckung in NP-Hard ist. Wir müssen beweisen, dass es auch in NP ist, um zu zeigen, dass es NP-vollständig ist. Ich finde das relativ einfach. Wenn Sie dafür Hilfe benötigen, gebe ich Ihnen einige Tipps.
quelle
Die Teilmengen-Summe kann leicht aus dem Partitionsproblem transformiert werden. Der Beweis, Exact Cover darauf zu reduzieren, ähnelt dem von 3-Dimensional Matching, und Sie finden ihn im Lehrbuch von Garey und Johnson. Der Beweis ist etwas kompliziert.
quelle