Reduktion von vc bis {a, k |A ist eine 3DNF (disjunktive Normalform), und es gibt einen Auftrag, der exakte K-Klausätze in einem} erfüllt

Question

Ich habe die folgende Frage:

\ beginnen {ALIGN} L_2={a, k \ \ Mid \ Text {A ist eine 3DNF (disjunktive Normalform) und} \\ \ text {Es gibt ein Zuweisung $ Z $, der genau $ k $ -klauseln in} \} ist \ END {ALIGN}

Ich weiß, dass $ l_2 \ in $ npc.

Zeigen Sie, dass $ l_2 \ in $ NP relativ einfach ist, werde ich diesen Teil überspringen.

Ich versuche, diesen $ l_2 \ in $ npc mit einer Reduktion von VC $ \ leq_p l_2 $ (VC ist eine Vertex-Abdeckung, die wir in seinem NPC kennen)

Ich habe die folgende Funktion definiert $ F $ :

$$ f (g, k)= (a, k) $$

Ich dachte an so etwas für jeden Knoten $ i $ in $ g $ Definieren Sie a Literal $ x_i $ , und machen Sie es im 3DNF-Format, $ a=Bigvee (x_i \ wedge x_i \ wedge x_i) $ wo $ 1 \ leq i \ leq n $ wo $ n $ die Anzahl von ist Knoten in $ g $ . Wir können das Folgendes definieren, das folgende $ z Container "> $ K $ Klauseln, geben Sie einfach $ 1 '$ wörtliche $ x_i $ so dass der Knoten $ i $ in der VC ist, und $ '0' $ Ansonsten, so Ein solcher $ Z $ existiert.

so einfach zu sehen, dass $ (g, k) \ in $ vc $ \ impliziert (A, K) \ in l_2 $ Seit wir explizit als $ Z $ gezeigt haben, der genau das $ k $ sichert> Klauseln.

Aber ich bin mir nicht sicher, dass die andere Seite $ (g, k) \ nicht \ in $ vc $ \ Impliziert (a, k) \ nicht \ in l_2 $ Wir haben ein Diagramm angegeben, das keine VC in der Größe $ K $ hat, aber ich denke fällt an Zu meinem Bau eines ( $ a=Bigvee (x_i \ wedge x_i \ wedge x_i) $ ) finden wir $ z sichern Sie sich $ x $ Clauses, wo $ 1 \ leq x \ leq n $ wo $ N $ ist die Anzahl der Knoten in $ g $ .

also hält meine Reduktion nicht?

Answer 1

Der Grund dafür, warum Sie Probleme haben, ist, dass Ihre Lösung nicht funktioniert. Das Problem ist insbesondere, dass Ihre Formel die VC-Problemanweisung nicht erfasst. Genauer gesagt, die von Ihnen bauende Formel haben immer Aufgaben, die $ K $ Clauses mit einfacher Einstellung $ K $ Variablen zu true und der Rest zu falsch.

Also let $ g= (v, e) $ ein Diagramm und $ x \ Subseteq V $ Seien Sie ein VC in $ g $ . Dann müssen für jede Kante $ VW \ in E $ $ v \ in x $ oder $ w \ in x $ , geben Sie uns 3 gegenseitig ausschließliche Möglichkeiten an (indem Sie im Wesentlichen umschreiben $ V \ Vee W $ in DNF):

.
• $ v \ in x $ aber $ W \ NOTIN X $ ,
• $ v \ NOTIN X $ aber $ w \ in x $
• $ v \ in x $ und $ w \ in x $

Daher ist der Rand $ VW $ von $ x $ falls und nur wenn die Formel < Span-Klasse="Math-Container"> $ \ psi (vw)= (v \ wedge w) \ Vee (\ neg v \ wedge w) \ Vee (v \ wedge \ neg w) $ hat genau eins Zufriedene Klausel (unter der Zuordnung, die dem $ x $ ) ist.

Bauen Sie eine solche Formel für jede Kante und nehmen ihre Disjunktion auf, erhalten wir die DNF-Formel $$ \ PSI ^ \ Text {VC} (g)=Bigvee_ {E \ in E} \ psi (e)=Bigvee_ {VW \ in E} (v \ wedge w) \ Vee (\ neg v \ wedge w) \ vee (v \ wedge \ neg w) $$ Und jeder Auftrag, der genau $ | E | $ -Klauungen erfüllt, muss ein vc von $ g $ sein. Jetzt brauchen wir einen Weg, um die Größe des VC in alles zu codieren, für die wir Ihre Idee wiederverwenden können. Definieren $$ \ psi (g)=psi ^ \ text {vc} (g) \ Vee \ Bigvee_ {v \ in v} V $$ und beachten Sie, dass die Anzahl der erfüllten Klauseln im zweiten Teil nur durch die Größe des Satzes von Eckpunkten gegeben wird, die wir auswählen, sodass die Gesamtzahl der erfüllten Klauseln unter der Zuweisung, die einem bestimmten VC- $ X $ in $ g $ ist $ | e | + | X | $ .

Hier bleibt nur ein Problem. Wir könnten einen Auftrag erhalten, der einem VC nicht entspricht, sondern mehr Scheitelpunkte einschließlich der gleichen Anzahl von Klauseln, die eine gewünschte VC erfüllen würde. Als Mittel können wir die erste Formel einiger $ | v | wiederholen + 1 $ mal so, dass egal wie viele Scheitelpunkte Sie ausgewählt haben, die Gesamtzahl der zufriedenen Klauseln immer zu niedrig ist.

somit erhalten wir die endgültige formel $$ \ PSI ^ \ AST (G)=Bigvee_ {i= 1} ^ {| V | + 1} \ psi ^ \ text {vc} (g) \ vee \ bigvee_ {v \ in v} v $$ und beachten Sie, dass, wenn $ g $ einen vc- $ x $ hat, dann erfüllt die entsprechende Zuordnung genau $ (| V | + 1) \ CDOT | E | + | X | $ Klauseln von $ \ psi ^ \ AST (g) $ . Seien Sie für die umgekehrte Richtung $ \ alpha $ einige Aufgabe, die $ (| V | + 1) \ CDOT | | + K $ Klauseln von $ \ psi ^ \ ast (g) $ . Dann muss $ \ alpha $ einen vc in g so ansonsten darstellen, die Anzahl der zufriedenen Klauseln im ersten Teil des $ \ PSI ^ \ AST (G) $ ist höchstens $ (| V | + 1) \ CDOT (| E | - 1)= | V | \ cdot | e | + | E | - | v | - 1 $ und als $ \ alpha $ kann höchstens $ | v | $ erfüllt werden Klauseln Im zweiten Teil wird die Gesamtzahl der zufriedenen Klauseln höchstens sein $$ (| V | + 1) \ CDOT (| E | - 1) + | V |= | V | \ cdot | e | + | E | - 1 <(| v | + 1) \ CDOT | E | $$ Dies bedeutet jedoch, dass die Gesamtzahl der zufriedenen Klauseln im ersten Teil genau sein muss $ (| V | + 1) \ CDOT | E | $ und damit genau < Span-Klasse="Math-Container"> $ K $ Klauseln des zweiten Teils sind erfüllt von $ \ alpha $ , so $ \ alpha $ entspricht einem vc $ x_ \ alpha $ der Größe $ k $ in $ g $ .

Beachten Sie, dass ich für Klarheit nicht einen $ 3 $ -dnf-Formel angegeben habe. Da alle Klauseln in $ \ psi ^ \ ast (g) $ in den meisten $ 2 $ $ Sie können jus

T Fügen Sie den Klauseln redundante Literale hinzu, um sie auf Größe zu blasen $ 3 $ , falls vorhanden.

Ich bin nicht sicher, dass dies der beste Weg ist, dies zu tun, aber es sollte trainieren.Ich habe einige Details für Kürze weggelassen, bitte fühlen Sie sich frei, um weitere Klarstellungen zu fragen, wenn Ihnen etwas nicht klar ist :)