Beweisen Sie die NP-Vollständigkeit der Entscheidung über die Erfüllbarkeit der monotonen Booleschen Formel

12

Ich versuche, dieses Problem zu lösen, und ich kämpfe wirklich.

Eine monotone Boolesche Formel ist eine Formel in der Aussagenlogik, in der alle Literale positiv sind. Beispielsweise,

(x1x2)(x1x3)(x3x4x5)

ist eine monotone Boolesche Funktion. Auf der anderen Seite so etwas wie

(x1x2x3)(¬x1x3)(¬x1x5)

ist keine monotone Boolesche Funktion.

Wie kann ich die NP-Vollständigkeit für dieses Problem nachweisen:

Bestimmen Sie, ob eine monotone Boolesche Funktion erfüllt werden kann, wenn Variablen oder weniger auf .k1

Es ist klar, dass alle Variablen nur positiv gesetzt werden können, und das ist trivial. Deshalb gibt es die Einschränkung, dass Variablen positiv gesetzt werden.k

Ich habe eine Reduktion von SAT auf monotone Boolesche Formel versucht. Ich habe versucht, jedes negative Literal durch eine Dummy-Variable zu ersetzen. Ich habe zum Beispiel versucht, durch ersetzen , und dann versucht, und als unterschiedliche Werte zu erzwingen . Ich habe es nicht ganz geschafft, das zum Laufen zu bringen.¬x1z1x1z1

nat
quelle
Herzlich willkommen! Bitte achten Sie genauer auf Sprache und Formatierung.
Raphael

Antworten:

12

Das "übergeordnete Element" des Problems, das Sie betrachten, wird manchmal als gewichtete Zufriedenheit (WSAT, insbesondere bei parametrisierter Komplexität) oder Min-Ones (obwohl dies normalerweise eine Optimierungsversion ist, aber nahe genug) bezeichnet. Diese Probleme haben die Einschränkung "höchstens Variablen auf true gesetzt" als ihr definierendes Merkmal.k

Die Beschränkung auf monotone Formeln ist tatsächlich überraschend leicht zu beweisen, man muss nur für einen Moment außerhalb der Erfüllbarkeitsprobleme stehen. Anstatt zu versuchen, eine SAT-Instanz zu ändern, beginnen wir stattdessen mit Dominating Set (DS).

Sehen Sie, ob Sie es von dort bekommen können. Mehr steckt in den Spoilern, in Stücke zerbrochen, aber meide sie, wenn du kannst. Ich zeige keine Mitgliedschaft in NP, damit solltest du kein Problem haben.

Bei einer Instanz von DS (dh wir wollen höchstens eine dominierende Menge von Größen k für ) können wir eine Instanz von WSAT konstruieren, wobei die Formel eine monotone CNF-Formel ist:(G,k)kG(ϕ,k)ϕ

Die Grundkonstruktion:

Für jedes wir eine Variable v 'var ( ϕ ) , für jedes v V ( G ) haben wir eine Klausel c v = u N ( v ) u ' .vV(G)vvar(ϕ)vV(G)cv=uN(v)u

Eine Skizze des Beweises:

Jeder Scheitelpunkt muss sich entweder in der dominierenden Menge befinden oder einen Nachbarn haben. Wenn wir also Scheitelpunkte finden, die eine dominierende Menge bilden, können die entsprechenden k Variablen in ϕ auf true gesetzt werden , und jede Klausel muss mindestens enthalten einer von ihnen. In ähnlicher Weise entsprechen die wahren Variablen, wenn es ein Gewicht k gibt, das die Zuweisung erfüllt, den Scheitelpunkten, die wir in der dominierenden Menge platzieren - jeder Satz c v muss mindestens einen haben, so dass jedes v (für sich oder auf andere Weise) dominiert wird.kkϕkcvv

Luke Mathieson
quelle
Wow das macht so viel mehr Sinn, danke! Ich glaube, ich war definitiv damit beschäftigt, SAT auf die monotone Boolesche Formel zu reduzieren.
nat
Ich sehe auch, dass wir die Vertex-Abdeckung auf die monotone Boolesche Formel reduzieren können.
nat
1
@nat in der Tat ist das Gehen von der Scheitelpunktabdeckung auch nett, weil es Ihnen eine Formel in 2CNF gibt, die interessant ist, wie 2-SAT in P ist, aber monotone WSAT mit 2CNF-Formeln ist NP-vollständig. Zufälligerweise können Sie auch antimonotone Ergebnisse (bei denen jede Variable negiert wird, Sie jedoch mindestens echte Variablen wünschen ) aus dem Clique / Independent-Set erhalten. Wenn Sie besonders daran interessiert sind, sollten Sie sich mit der parametrisierten Komplexität befassen, bei der diese Art von Erfüllbarkeitsproblemen eine zentrale Rolle spielt. k
Luke Mathieson
Ich denke, dass genau der gleiche Ansatz bei der Abdeckung von Vertikeln funktioniert.
Haskell Fun
@HaskellFun, darüber habe ich auch nachgedacht. Die Vertex-Abdeckung entspricht der monotonen Min-W2SAT-Abdeckung.
Rus9384
2

Es gibt eine einfache Reduzierung von SAT. Einführung einer neuen Variablen darstellen ¬ x i . Bei gegebener Formel ϕ erstellen wir eine neue Formel ϕ ′, indem wir jedes Vorkommen von ¬ x i durch z i ersetzen und die Klausel x iz i für jede Variable hinzufügen . Wir setzen k als Anzahl der ursprünglichen Variablen. Die neue Formel ϕ ist monoton und kann mit höchstens k Variablen erfüllt werden, die genau dann auf wahr gesetzt sind, wenn ϕ erfüllt werden kann. (Dies liegt daran, dass die kzi¬xiϕϕ¬xizixizikϕϕkDisjunktionsklauseln bewirken, dass ϕ mindestens k Variablen für True hat; aber dann ist die einzige Möglichkeit, höchstens k zu haben, genau eines von ihnen für jedes Paar auf wahr zu setzen {x_i, z_i}.)xiziϕkk

David
quelle