Das Schlag-Set-Problem (HS) ist wie folgt definiert. Sei $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ Sammlung einer Teilmenge von S, dh $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Wir möchten wissen, ob $ {S} „\ subset S $ existiert, wobei $ | {S} „| < k $, so dass $ S_i \ cap S „\ neq \ Emptyset $, $ i = 1,2, …, m. $
Beweisen Sie, dass HS Np-vollständig ist.
Hinweis : Wenn $ | S_i | = 2 $, HS wird zu Vertex Cover, von dem bereits bekannt ist, dass es NP-vollständig ist.
Kommentare
- Was haben Sie versucht? Wo haben Sie es getan? Wir ' helfen Ihnen gerne beim Verständnis der Konzepte, aber es ist unwahrscheinlich, dass Sie nur Übungen für Sie lösen. Möglicherweise finden Sie Diese Seite ist hilfreich bei der Verbesserung Ihrer Frage.
Antwort
3SAT wird auf das Schlagen reduziert Problem setzen. Wenn ein 3SAT $ \ phi $ $ m $ -Klauseln und $ n $ -Variablen enthält, definieren Sie
$$ S = \ {x_1, \ dots x_n, \ overline {x_1}, \ dots, \ overline {x_n} \} $$ $$ S_i = \ {y_1, y_2, y_3 \}, \ text {if} y_1, y_2, y_3 \ in S \ text {und} (y_1 \ lor y_2 \ lor y_3) \ text {ist eine Klausel.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {für alle Variable} x. $$ $$ k = n $$
Angenommen, $ \ phi $ ist erfüllbar, dann gibt es eine True-Value-Zuweisung für $ n $ -Variablen. Fügen Sie also $ x $ zu $ S „$ hinzu, wenn $ x = true $, andernfalls $ \ overline {x} $ zu $ S“ $.
Nehmen wir nun an, das HS-Problem hat eine Lösung $ S „$. Da dann für jede Variable $ x $, $ S“ \ cap S_x \ neq \ Emptyset $, $ S „$ mindestens $ n $ Literale der Form $ x $ oder $ \ overline {x} $ hat für jede Variable $ x $. Außerdem dürfen keine $ x $ und $ \ overline {x} $ gleichzeitig zu $ S „$ gehören, da die Größe von $ S“ $ höchstens $ n $ beträgt Jede Klausel $ C_i $, $ S „\ cap S_i \ neq \ Emptyset $. Daher wählen wir für jede Klausel $ y_i \ in S“ \ cap S_i $ aus und setzen $ x = true $, wenn $ y_i = x $ und $ x = false $ if $ y_i = \ overline {x} $.
Kommentare
- Können Sie eine positive und eine negative Instanz anzeigen?
Antwort
Es ist leicht zu zeigen, dass sich Hitting Set in NP befindet. Eine Lösung muss nur das Set H aufweisen – Man kann leicht in Polynomzeit überprüfen, ob H die Größe k hat und jede der Mengen B1, …, Bm schneidet.
Wir reduzieren von der Scheitelpunktabdeckung. Betrachten Sie eine Instanz des Scheitelpunkts Deckungsproblem – Graph G = (V, E) und eine positive ganze Zahl k. Wir ordnen es wie folgt einer Instanz des Schlagmengenproblems zu. Die Menge A ist die Menge der Eckpunkte V. Für jede Kante e ∈ E haben wir eine Menge Se, die aus den beiden Endpunkten von e besteht. Es ist leicht zu erkennen, dass eine Menge von Eckpunkten S eine Eckpunktabdeckung von G ist, wenn die entsprechenden Elemente eine Schlagmenge in der Schlagmengeninstanz bilden.
Kommentare
- Willkommen bei ComputerScience @ SE. Interessante Verwendung des speziellen Symbols
∈– Es ist üblich, MathJax zu verwenden, um beispielsweise eine ordnungsgemäße Subskription zu ermöglichen: $ B_1, \ dots, B_m $. - Was wäre wenn Größe von Se ist größer als 2? Wird es funktionieren?
Antwort
Das Problem mit dem Schlagsatz entspricht dem definierten Problem mit der Deckungsabdeckung wie folgt:
EINGABE: eine Sammlung C von Teilmengen einer endlichen Menge S.
LÖSUNG: Eine Mengenabdeckung für S, dh eine Teilmenge $ C „\ subseteq C $ wie z dass jedes Element in S zu mindestens einem Mitglied von $ C „$ gehört.
Wenn $ k $ gegeben ist, existiert eine festgelegte Abdeckung $ C“ $, so dass $ \ vert C „\ vert \ leq k $?
Dies sieht aus wie eine Hausaufgabe, daher möchte ich Sie herausfinden lassen, wie Sie eine gegebene Instanz von Set Cover in eine äquivalente Instanz von Hitting Set konvertieren können.
Andernfalls, wenn Wenn Sie dem Hinweis folgen möchten, zeigen Sie zuerst, dass das Schlagen in $ NP $ eingestellt ist. Dies ist eine Lösung, die Sie in Polynomzeit überprüfen können.
Dann zeigen Sie das mit einem Diagramm $ G. = (V, E) $, das Finden einer Scheitelpunktabdeckung der Größe $ k $ entspricht dem Finden einer Treffermenge der Größe $ k $. Das heißt, wenn $ | E | = m $, können Sie eine schlagende Mengeninstanz mit der gleichen Anzahl von Mengen erstellen.