An Efficient Algorithm for Solving the 2-MAXSAT Problem

Technische Zusammenfassung: Ein effizienter Algorithmus zur Lösung des 2-MAXSAT-Problems

Problemdefinition
Die Arbeit befasst sich mit dem 2-MAXSAT-Problem, einer eingeschränkten Version des Maximum-Satisfiability-Problems (MAXSAT). Gegeben sei eine Menge $V$ von $m$ Boole’schen Variablen und eine Sammlung $C$ von $n$ Klauseln in Konjunktiver Normalform (KNF), wobei jede Klausel höchstens zwei Literale enthält. Das Ziel ist es, eine Belegung zu finden, die die Anzahl der erfüllten Klauseln maximiert. Das Problem wird selbst unter dieser Einschränkung als NP-vollständig etabliert.

Methodik
Der vorgeschlagene Algorithmus weicht von traditionellen Branch-and-Bound- oder Approximationsmethoden ab, indem er das Problem in eine DNF-Maximierungsaufgabe (Disjunktive Normalform) transformiert und eine spezialisierte graphbasierte Suchstruktur verwendet. Die Methodik verläuft in drei Hauptphasen:

1. Transformation zu DNF:
   Der Algorithmus konstruiert eine neue Formel $D$ in DNF aus der ursprünglichen KNF-Formel $C$. Für jede Klausel $C_i = l_{i1} \lor l_{i2}$ in $C$ führt der Algorithmus eine neue Hilfsvariable $x_i$ ein und erzeugt zwei Konjunktionen: $D_{i1} = l_{i1} \land x_i$ und $D_{i2} = l_{i2} \land \neg x_i$. Die resultierende Formel $D$ besteht aus $2n$ Konjunktionen. Proposition 1 in der Arbeit stellt fest, dass $C$ mindestens $n^*$ erfüllbare Klauseln besitzt, wenn und nur wenn $D$ unter einer Belegung für $V \cup \{x_1, \dots, x_n\}$ mindestens $n^*$ erfüllbare Konjunktionen besitzt.

2. Graphrepräsentation (p-Graphen und Tries):*
   Um die Belegungen, die die Konjunktionen in $D$ erfüllen, effizient zu repräsentieren, führt die Arbeit den p-Graphen* ein.

• Variablensequenzen: Jede Konjunktion wird in eine sortierte Variablensequenz basierend auf der globalen Häufigkeit des Auftretens von Variablen umgewandelt. Negative Literale werden durch die Einführung einer speziellen Notation $(c, *)$ behandelt, die darstellt, dass die Variable $c$ entweder wahr oder falsch sein kann (oder übersprungen werden kann), ohne die Wahrheit der Konjunktion zu beeinflussen.
• p-Graphen: Ein gerichteter Graph, der eine einzelne Konjunktion repräsentiert, wobei Knoten den Variablen in der Sequenz entsprechen. „Spans“ (Kanten, die Variablen überspringen) repräsentieren die $(c, *)$-Optionen.
• p-Graphen:* Eine Verfeinerung von p-Graphen, bei denen „überlappende Spans“ (aufeinanderfolgende optionale Variablen) mittels transitiiver Hülle zusammengeführt werden. Dies stellt sicher, dass der Graph alle gültigen Belegungen für eine spezifische Konjunktion korrekt repräsentiert.
• Trie-ähnliche Struktur ($G$): Alle p*-Graphen werden in einen einzigen Trie-ähnlichen Graphen $G$ integriert. Diese Struktur gruppiert gemeinsame Variablensequenzen, um redundante Prüfungen zu vermeiden. Der Graph enthält „Verzweigungsknoten“, an denen Pfade divergieren.

3. Rekursiver Bottom-Up-Suchprozess:
   Der Kernalgorithmus SEARCH(G) exploriert den Graphen $G$ in einer Bottom-Up-Manier (Post-Order-Traversierung), um die maximale Teilmenge erfüllbarer Konjunktionen zu finden.

• Erreichbare Teilmengen (RS): Für einen Verzweigungsknoten $v$ berechnet der Algorithmus „erreichbare Teilmengen“ (Reachable Subsets, RS) von Knoten, die über Spans von Vorfahren erreichbar sind. Diese Teilmengen repräsentieren Gruppen von Konjunktionen, die gleichzeitig erfüllt werden können, indem bestimmte Variablen übersprungen werden.
• Obere Grenzen (upBounds): Basierend auf RSs identifiziert der Algorithmus „obere Grenzen“ – Mengen von Knoten, die das Verschmelzen von Subgraphen ermöglichen.
• Rekursive Konstruktion: Wenn ein Verzweigungsknoten auftritt, konstruiert der Algorithmus einen neuen, kleineren Trie-ähnlichen Subgraphen, der in den Knoten der oberen Grenze wurzelt. Eine virtuelle Wurzel (der ursprüngliche Verzweigungsknoten) wird hinzugefügt, um die Konnektivität aufrechtzuerhalten. Der Algorithmus ruft SEARCH rekursiv auf diesen Subgraphen auf.
• Optimierung: Um redundante Berechnungen zu verhindern, nutzt der Algorithmus zwei Verbesserungen: (1) die Begrenzung der RS-Berechnungen auf das Segment zwischen dem aktuellen Verzweigungsknoten und seinem untersten Vorfahren-Verzweigungsknoten und (2) die Verwendung eines Hash-Arrays, um die Ergebnisse zuvor besuchter Subgraphen zu cachen, wodurch wiederholte rekursive Aufrufe unterdrückt werden.

Wesentliche Beiträge

• Transformationstechnik: Eine Reduktion des 2-MAXSAT-Problems in ein Problem der Maximierung erfüllbarer Konjunktionen in DNF in Polynomialzeit.
• p-Graph-Struktur:* Die Definition von p*-Graphen und deren transitive Hülle zur präzisen und kompakten Repräsentation von Belegungen für Konjunktionen, die optionale Variablen enthalten.
• Rekursiver Trie-Suchalgorithmus: Ein neuartiger rekursiver Algorithmus, der dynamisch eine Trie-ähnliche Graphstruktur aufbaut und durchsucht, wobei er „erreichbare Teilmengen“ und „obere Grenzen“ nutzt, um Lösungsräume effizient zu mergen.
• Komplexitätsanalyse: Die Arbeit liefert eine detaillierte Analyse, die behauptet, dass der Algorithmus innerhalb von Polynomialzeit-Grenzen operiert.

Ergebnisse und Komplexität
Die Arbeit behauptet, dass die Worst-Case-Zeitkomplexität des vorgeschlagenen Algorithmus durch $O(n^2 m^4)$ begrenzt ist, wobei $n$ die Anzahl der Klauseln und $m$ die Anzahl der Variablen ist.

• Die Konstruktion des initialen Tries und der p*-Graphen benötigt $O(nm^2)$.
• Die rekursive Suche beinhaltet höchstens $O(nm)$ Verzweigungsknoten.
• Jeder Verzweigungsknoten ist aufgrund der Reduktion der Graphhöhe in jedem Schritt an höchstens $O(m)$ rekursiven Aufrufen beteiligt.
• Die Kosten für die Konstruktion eines Subgraphen pro Aufruf betragen $O(nm^2)$.
• Die Kombination dieser Faktoren ergibt die Schranke von $O(n^2 m^4)$.

Bedeutung und Behauptungen
Die Arbeit schließt mit der Feststellung, dass da das 2-MAXSAT-Problem als NP-vollständig bekannt ist, die Existenz eines Polynomialzeit-Algorithmus zur Lösung desselben einen Beweis für P = NP darstellt. Die Autoren geben an, dass dieses Ergebnis einen Beweis für P = NP liefert und das Verständnis der computergestützten Komplexität für Erfüllbarkeitsprobleme grundlegend verändert. Die Arbeit wird als Modifikation und Erweiterung eines Konferenzpapers präsentiert, unterstützt durch NSERC, Kanada.