Reduzierung der exakten Deckung auf die Teilmenge

7

Zeigen Sie, dass das Teilmengen-Summenproblem (Gegeben eine Folge von ganzen Zahlen S=i1,i2,,in und eine ganze Zahl kGibt es eine Folge von S das summiert sich genau k?) ist NP-vollständig.

Hinweis: Verwenden Sie das genaue Deckungsproblem.

Das genaue Deckungsproblem ist das folgende: Bei einer Familie von Sets S1,S2,,Sn Gibt es eine Mengenabdeckung, die aus einer Unterfamilie paarweise disjunkter Mengen besteht?

Zunächst einmal, um zu zeigen, dass dieses Problem vorliegt NP 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 S und die Nummer k so dass jede Zahl einer Menge von Elementen und entspricht kentspricht dem gesamten Satz. Angenommen, es gibtn Elemente und k verschiedene Sätze.

Wir ersetzen jeden Satz S durch eine Zahl, die ist 1 in seiner i-ten Position, wenn ich in S bin und a hat 0 in seiner i-ten Position anders.

Wir setzen k auf eine Zahl, die ist n Kopien der Nummer 1.

Mary Star
quelle
1
Versuchen Sie zu beweisen, dass Ihre Reduzierung funktioniert. Wenn Sie erfolgreich sind, werden Sie wissen, dass dies der Fall ist. Ansonsten zurück zum Zeichenbrett.
Yuval Filmus

Antworten:

5

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,4und die Sätze sind

  • S1={3,4}
  • S2={3}

Die Reduktion auf die Teilmengen-Summe sind die Zahlen 7,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 folgende3kann 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- -1Sä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 1erscheint, 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 die ich-th Element im genauen Deckungsproblem hat einen Wert von 2ichn. 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.

Christopher Boo
quelle
4

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.

Bangye
quelle