Findet eine Lösung für ein System von 2sat-Gleichungen, das von oder (DNF-Formular) in NP separatiert ist

Question

Ich möchte wissen, ob Sie eine Lösung für eine bestimmte Anzahl von 2sat-Gleichungen, das mit oder mit dem Gatter getrennt ist (DNF-Form wie unten), in P oder NP ist.

Die Gleichung hat insgesamt n Variablen und jede Klausel ist eine 2sat-Gleichung an sich in einer Teilmenge von Variablen von 1 bis N. Beispiel:

f= [(x1 || x2) && (! x2 || x3) && (x3 || x4)] ||[(x2 || x5) && (x3 || x6) && (! x4 ||! x6)] ||....

Die Gleichung F ist ein DNF von 2sat-Gleichungen, das M-Klauseln gesagt hat.Ist es in NP eine Lösung zu finden?Wenn ja wie?

auch, insbesondere ich möchte auch wissen, ob falsche Instanzen der Gleichung F in P oder NP ist.

Answer 1

.
• Zunächst möchte ich feststellen, dass der Titel der Frage ein bisschen irreführend ist, da $ P $ eine Teilmenge von $ ist NP $ . Siehe auch Kommentar von Yuval Filmus. Ich gehe davon aus, was Sie beabsichtigen zu stellen ist, ob es in $ p $ oder in $ np \ ist setminus p $ .
• Auch der Name "DNF" bezieht sich insbesondere auf einen Disjunktion von elementaren

mit dem aus dem Weg, hier ist meine Antwort.

---

.

1. Um einen Disjunkt von 2-CNFs zu erfüllen, ist alles, was Sie brauchen, um eins von ihnen zu befriedigen. Wenn Sie also den 2-Sat-Algorithmus an den ersten der CNFs anwenden und ein "Ja" erhalten, ist die Antwort auf das gesamte Problem "Ja". Ansonsten bewegen Sie sich einfach zum zweiten und so weiter. Sollte nicht lange dauern, da Sie nur m von ihnen haben. Wenn keiner von ihnen individuell zufrieden sein kann, d. H. Sie sind alle konstanten Nullen, dann ist offensichtlich das gesamte Ding eine konstante Null.

   Die Antwort auf den ersten Teil ist: Das Problem ist in P, mit dem folgenden Entscheidungsalgorithmus:

   Wenden Sie für jedes 2-CNF den "normalen" 2-Sat-Algorithmus (der Auflösungsregel) auf, um festzustellen, ob er erfüllt ist oder nicht. Wenn "Ja", rufen Sie einfach "Ja" zurück. Wenn Sie alle durchlaufen, ohne ein "Ja" zu finden, dann kehren Sie "Nein" zurück.

---

2. Nun, die "falsche" Fälle dieser Formel (auch als Problem der Tautologie genannt) finden, ist eine andere Frage ganz. Zum einen entspricht Tautologie für die ORs von An- und ORS der Erfüllung von Ands von Anden von An und Ans von De Morgan von de Morgan. Aber das ist nur ein allgemeinerer Fall eines bereits allgemeinen SAT-Problems, nicht wahr?

   Überlegen Sie, was passiert, wenn Sie die Menge möglicher Formeln auf diejenigen einschränken, in denen jeder Zwei-Element-Disjunkt wirklich nur ein Element ist, das wiederholt ist. Es ist also eine Formel $$ F= [(x_1 \ vee x_1) \ & (\ neg x_2 \ vee \ neg x_2) \ & (x_3 \ vee x_3)] \ Vee [(x_2 \ vee x_2) \ & (x_4 \ vee x_4) \ & (x_4 \ vee x_4) \ & ( x_5 \ vee x_5)] \ vee ... $$ das ist gleichwertig $$ F= [x_1 \ & \ neg x_2 \ & x_3] \ Vee [x_2 \ & x_4 \ & x_5] \ vee ... $$ Das ist nur ein normaler DNF. Nach der De Morgan-Transformation erhalten Sie einen normalen CNF, dessen Befriedigung als NP-Hard ist. Daher ist auch jedes Problem, das diese ein als Teilmenge enthält, auch mindestens NP-HARD.

   Natürlich ist das betreffende Problem nicht außerhalb von np, da es noch polynomial überprüfbar ist. Die Antwort auf Ihre zweite Frage lautet also "in NP, aber nicht in P".