Gibt es einen manchmal effizienten Algorithmus, um #SAT zu lösen?

24

Sei eine Boolesche Formel, die aus den üblichen Operatoren AND, OR und NOT und einigen Variablen besteht. Ich möchte die Anzahl der zufriedenstellenden Aufgaben für . Das heißt, ich möchte die Anzahl der verschiedenen Zuordnungen von Wahrheitswerten zu den Variablen von für die einen wahren Wert annimmt. Zum Beispiel hat die Formel drei befriedigende Zuordnungen; hat vier. Dies ist das # SAT-Problem .B B B a ∨ b ( a ∨ b ) ∧ ( c ∨ ¬ b )BBBBa∨b(a∨b)∧(c∨¬b)

Offensichtlich würde eine effiziente Lösung für dieses Problem eine effiziente Lösung für SAT bedeuten, was unwahrscheinlich ist, und in der Tat ist dieses Problem # P-vollständig und daher möglicherweise strenger als SAT. Ich erwarte daher keine garantiert effiziente Lösung.

Es ist jedoch bekannt, dass es relativ wenige wirklich schwierige SAT-Fälle gibt. (Siehe zum Beispiel Cheeseman 1991, "Wo die wirklich schwierigen Probleme liegen" .) Eine einfache Suche kann viele Fälle effizient lösen, auch wenn sie im schlimmsten Fall exponentiell ist. Obwohl die Auflösungsmethoden im schlimmsten Fall exponentiell sind, sind sie in der Praxis noch effizienter.

Meine Frage ist:

Sind Algorithmen bekannt, mit denen die Anzahl der erfüllenden Zuweisungen einer typischen Booleschen Formel schnell gezählt werden kann, selbst wenn solche Algorithmen im Allgemeinen eine exponentielle Zeit benötigen? Gibt es etwas auffallend Besseres, als jede mögliche Aufgabe aufzuzählen?

complexity-theory reference-request satisfiability Mark Dominus
quelle
1
Ich habe versucht, ein Tag zur # p-Vollständigkeit hinzuzufügen, aber die Stack Exchange-Software mag das # -Zeichen nicht.
Mark Dominus
Ich würde mit der Behauptung vorsichtig sein, dass "es relativ wenige wirklich schwierige Fälle von SAT selbst gibt". Ich glaube, das Papier, das Sie verlinken, spricht tatsächlich von zufälligem SAT. Darüber hinaus gilt das Phasenübergangsphänomen nur für die zufälligen Instanzen. Es gibt viele wirklich harte handgefertigte, industrielle usw. Instanzen von SAT. k
Juho
Vielen Dank. Denken Sie, dass dies dazu führt, dass meine Frage weniger klar wird? Verstehst du was ich verlange?
Mark Dominus
Es ist mir klar. Es ist nur wichtig, sich daran zu erinnern, welche Instanzen den Phasenübergang aufweisen :)
Juho

Antworten:

21

Zählen im allgemeinen Fall

Das Problem, an dem Sie interessiert sind, wird als #SAT oder Modellzählung bezeichnet. In gewissem Sinne ist es das klassische # P-vollständige Problem. Modellzählung ist auch bei SAT schwierig! Es überrascht nicht, dass die genauen Methoden nur Instanzen mit rund Hunderten von Variablen verarbeiten können. Es gibt auch ungefähre Methoden, die möglicherweise Instanzen mit etwa 1000 Variablen verarbeiten können.2

Genaue Zählmethoden basieren oft auf einer umfassenden Suche nach DPLL oder einer Art Wissenskompilierung. Die ungefähren Methoden werden normalerweise als Methoden kategorisiert, die schnelle Schätzungen ohne Garantien liefern, und Methoden, die Unter- oder Obergrenzen mit einer Richtigkeitsgarantie versehen. Es gibt auch andere Methoden, die möglicherweise nicht zu den Kategorien passen, z. B. das Erkennen von Hintertüren, oder Methoden, die bestimmte Struktureigenschaften für die Formeln (oder deren Abhängigkeitsgraphen) benötigen.

Es gibt praktische Implementierungen. Einige genaue Modellzähler sind CDP, Relsat, Cachet, sharpSAT und c2d. Die Art der Haupttechniken, die von den exakten Lösern verwendet werden, sind Teilzählungen, Komponentenanalyse (des zugrunde liegenden Beschränkungsgraphen), Formel- und Komponenten-Caching und intelligentes Schließen an jedem Knoten. Eine andere auf Wissenskompilierung basierende Methode konvertiert die eingegebene CNF-Formel in eine andere logische Form. Aus dieser Form kann die Modellzahl leicht abgeleitet werden (Polynomzeit in der Größe der neu erstellten Formel). Beispielsweise könnte man die Formel in ein binäres Entscheidungsdiagramm (BDD) umwandeln. Man könnte dann die BDD vom "1" -Blatt zurück zur Wurzel überqueren. Oder für ein anderes Beispiel verwendet der c2d einen Compiler, der CNF-Formeln in deterministische zerlegbare Negationsnormalform (d-DNNF) umwandelt.

Wenn Ihre Instanzen größer werden oder es Ihnen nicht wichtig ist, genau zu sein, gibt es auch ungefähre Methoden. Mit ungefähren Methoden kümmern wir uns um die Qualität der Schätzung und das mit der von unserem Algorithmus gemeldeten Schätzung verbundene Korrektheitsvertrauen und berücksichtigen diese. Ein Ansatz von Wei und Selman [2] verwendet die MCMC-Abtastung, um eine Approximation der wahren Modellzahl für die Eingabeformel zu berechnen. Die Methode basiert auf der Tatsache, dass man eine gute Schätzung der Anzahl der Lösungen von berechnen kann , wenn man (fast-) gleichförmig aus dem Lösungssatz einer Formel kann .ϕϕ

Gogate und Dechter [3] verwenden eine Modellzähltechnik namens SampleMinisat. Es basiert auf der Abtastung aus dem rückverfolgungsfreien Suchraum einer Booleschen Formel. Die Technik baut auf der Idee einer wichtigen Neuabtastung auf und verwendet DPLL-basierte SAT-Löser, um den rückspurfreien Suchraum zu konstruieren. Dies kann entweder vollständig oder bis zu einer Annäherung erfolgen. Eine Bemusterung für Schätzungen mit Garantien ist ebenfalls möglich. Aufbauend auf [2] haben Gomes et al. [4] haben gezeigt, dass durch Stichproben mit einer modifizierten randomisierten Strategie eine nachweisbare Untergrenze der Gesamtmodellzahl mit hohen wahrscheinlichkeitstheoretischen Korrektheitsgarantien erreicht werden kann.

Es gibt auch Arbeiten, die auf der Verbreitung von Überzeugungen aufbauen. Siehe Kroc et al. [5] und den von ihnen eingeführten BPCount. In derselben Veröffentlichung geben die Autoren eine zweite Methode namens MiniCount an, mit der die Anzahl der Modelle nach oben begrenzt werden kann. Es gibt auch einen statistischen Rahmen, mit dem man unter bestimmten statistischen Annahmen Obergrenzen berechnen kann.

Algorithmen für # 2-SAT und # 3-SAT

Wenn Sie Ihre Aufmerksamkeit auf # 2-SAT oder # 3-SAT beschränken, gibt es Algorithmen, die inO(1.3247n)O(1.6894n)O(1,6423n)

Wie es in der Natur des Problems liegt, hängt eine Menge von der Größe und Struktur Ihrer Instanzen ab, wenn Sie Instanzen in der Praxis lösen möchten. Je mehr Sie wissen, desto besser können Sie die richtige Methode auswählen.

[1] Vilhelm Dahllöf, Peter Jonsson und Magnus Wahlström. Zählen zufriedenstellender Aufgaben in 2-SAT und 3-SAT. In Proceedings of the 8th International Computing and Combinatorics Conference (COCOON-2002), 535-543, 2002.

[2] W. Wei und B. Selman. Ein neuer Ansatz für die Modellzählung. In Proceedings of SAT05: 8. Internationale Konferenz über Theorie und Anwendungen von Erfüllbarkeitstests, Band 3569, Lecture Notes in Computer Science, 324-339, 2005.

[3] R. Gogate und R. Dechter. Ungefähre Zählung durch Abtasten des rückverfolgungsfreien Suchraums. In Proceedings of AAAI-07: 22. Nationale Konferenz für künstliche Intelligenz, 198–203, Vancouver, 2007.

[4] CP Gomes, J. Hoffmann, A. Sabharwal und B. Selman. Vom Sampling bis zur Modellzählung. In Proceedings of IJCAI-07: 20. Internationale gemeinsame Konferenz für künstliche Intelligenz, 2293–2299, 2007.

[5] L. Kroc, A. Sabharwal und B. Selman. Nutzung von Glaubensvermehrung, Backtrack-Suche und Statistik für die Modellzählung. In CPAIOR-08: 5. Internationale Konferenz über die Integration von KI- und OP-Techniken in die Constraint-Programmierung, Band 5015 der Lecture Notes in Computer Science, 127–141, 2008.

[6] K. Kutzkov. Neue Obergrenze für das # 3-SAT-Problem. Information Processing Letters 105 (1), 1-5, 2007.

Juho
quelle
8

Neben den von Juho aufgelisteten Artikeln beschreiben einige weitere Arbeiten zu diesem Thema, insbesondere die Annäherung an die Anzahl der Lösungen:

DW
quelle