Kernalgorithmen wie DPLL und seine Verfeinerungen wie CDCL sind vollständig deterministisch.
Beachten Sie, dass Nichtdeterminismus nicht unbedingt bedeutet, dass ein Algorithmus zu einem falschen Ergebnis führen kann. Zum Beispiel können wir unterscheiden zwischen
Monte-Carlo-Algorithmen sind randomisierte Algorithmen, deren Ausgabemit einiger Wahrscheinlichkeit falsch sein kann .
Las Vegas-Algorithmen , bei denen es sich um randomisierte Algorithmen handelt, deren Ausgabe immer korrekt ist. Die Algorithmen spielen jedoch mit den für die Berechnung verwendeten Ressourcen, z. B. die Laufzeit bei identischen Eingaben.
Das andere Extrem sind probabilistische Algorithmen zur Lösung von Sat wie Schönings [1], das Monte-Carlo ist und in der Praxis aufgrund seiner äußersten Einfachheit bemerkenswert effektiv ist. Interessanterweise kann Schönings Algorithmus vollständig derandomisiert werden, ohne seine Wirksamkeit zu verlieren [2] [2].k
In der Praxis verwenden industrielle SAT-Löser immer ein gewisses Maß an Zufälligkeit, um dem schlechten (= exponentiellen) Worst-Case-Verhalten von DPLL-basierten Algorithmen zu entkommen. MiniSat ist eine hoch konfigurierbare und sich weiterentwickelnde Software. Allerdings ist MiniSat nicht vollständig deterministisch: Die Auswahl der Verzweigungsvariablen erfolgt je nach Befehlszeilenoptionen manchmal zufällig. (Standardmäßig werden 2% der Verzweigungsvariablen zufällig ausgewählt.) Ebenso hat MiniSAT die Möglichkeit, die VSIDS-Scores zufällig zu initialisieren. (VSIDS ist eine Heuristik zum "Messen" des Einflusses einer Variablen.)
Kann der Monte-Carlo-Algorithmus sagen, dass ein Problem SAT ist, wenn dies nicht der Fall ist, ohne Lösung der Erfüllbarkeit oder nur im Fall von unSAT, dass das Problem möglicherweise SAT ist?
Xavier Combelle
@XavierCombelle Das würde vom spezifischen Algorithmus abhängen, obwohl es mir schwer fällt, an einen Algorithmus zu denken, der SAT falsch machen könnte. Schönings macht nur unSAT falsch.
Martin Berger
Eine kleine Erweiterung - während MiniSat Zufälligkeit verwendet, ist es keine "wahre" Zufälligkeit. Jeder Lauf von MiniSat liefert dieselbe Antwort in derselben Zeitspanne (wenn Sie keine Optionen neu konfigurieren), da bei jedem Ausführen des Lösers dieselben "zufälligen" Auswahlmöglichkeiten ausgewählt werden.
Chris Jefferson
@ChrisJefferson Hat MiniSAT keine Möglichkeit, einen zufälligen Startwert anzugeben?
Martin Berger
6
Das ist richtig. DPLL erkundet den Raum ausführlich. Wenn es 'unsat' zurückgibt, gibt es sicherlich keine zufriedenstellende Zuordnung.
In jüngerer Zeit haben Forscher zertifizierende SAT-Löser entwickelt, die zusätzlich einen (hoffentlich kurzen) Nachweis der Unzufriedenheit liefern, wenn sie "unsat" zurückgeben. Dieser Beweis kann von jedem anderen überprüft werden. Auf diese Weise können andere überprüfen, ob die Formel nicht zufriedenstellend ist, ohne dass sie den SAT-Algorithmus erneut ausführen müssen. Dies kann in einigen Kontexten nützlich sein.
MiniSAT ist eher eine Implementierung als ein Algorithmus. Sein Verhalten hängt von seinem Code ab. Ich kann nicht mit dem Code sprechen.
Alle DPLL / CDCL-Löser können "erweitert" werden, um einen Nachweis der Unzufriedenheit zu erbringen.
Yuval Filmus
5
Ein Schlüsselwort, das Ihnen möglicherweise fehlt, ist die Vollständigkeit . Im Allgemeinen gilt ein Suchalgorithmus als vollständig, wenn er eine Lösung findet, sofern diese existiert (wenn genügend Zeit vorhanden ist). Insbesondere ist DPLL ein Beispiel für eine deterministische, vollständige Suchmethode.
SAT-Löser können deterministisch sein oder nicht, je nachdem, wie sie implementiert sind. Beachten Sie, dass der Nichtdeterminismus hier nur das generierte Modell beeinflussen kann, nicht die Antwort (SAT oder UNSAT) des Lösers! Für Diversifizierungszwecke und andere Zwecke führt der SAT-Löser im Allgemeinen an einem bestimmten Punkt Zufälligkeit ein: zum Beispiel, um variable Aktivitäten zu initialisieren oder zufällige Entscheidungen zu treffen. Im Minisat werden beispielsweise zufällige Entscheidungen getroffen, indem eine Funktion aufgerufen wird, die bei Verwendung desselben zufälligen Startwerts immer dieselbe Zufallszahl zurückgibt. Wenn Sie also zu diesem Zeitpunkt keine Konfiguration des Solvers ändern, haben Sie immer die gleiche Antwort und das gleiche Modell. Das Ändern des zufälligen Startwerts hat beispielsweise keine Auswirkungen auf die Antwort (SAT oder UNSAT), kann jedoch das Modell und die Ausführungszeit ändern.
Das ist richtig. DPLL erkundet den Raum ausführlich. Wenn es 'unsat' zurückgibt, gibt es sicherlich keine zufriedenstellende Zuordnung.
In jüngerer Zeit haben Forscher zertifizierende SAT-Löser entwickelt, die zusätzlich einen (hoffentlich kurzen) Nachweis der Unzufriedenheit liefern, wenn sie "unsat" zurückgeben. Dieser Beweis kann von jedem anderen überprüft werden. Auf diese Weise können andere überprüfen, ob die Formel nicht zufriedenstellend ist, ohne dass sie den SAT-Algorithmus erneut ausführen müssen. Dies kann in einigen Kontexten nützlich sein.
MiniSAT ist eher eine Implementierung als ein Algorithmus. Sein Verhalten hängt von seinem Code ab. Ich kann nicht mit dem Code sprechen.
quelle
Ein Schlüsselwort, das Ihnen möglicherweise fehlt, ist die Vollständigkeit . Im Allgemeinen gilt ein Suchalgorithmus als vollständig, wenn er eine Lösung findet, sofern diese existiert (wenn genügend Zeit vorhanden ist). Insbesondere ist DPLL ein Beispiel für eine deterministische, vollständige Suchmethode.
quelle
SAT-Löser können deterministisch sein oder nicht, je nachdem, wie sie implementiert sind. Beachten Sie, dass der Nichtdeterminismus hier nur das generierte Modell beeinflussen kann, nicht die Antwort (SAT oder UNSAT) des Lösers! Für Diversifizierungszwecke und andere Zwecke führt der SAT-Löser im Allgemeinen an einem bestimmten Punkt Zufälligkeit ein: zum Beispiel, um variable Aktivitäten zu initialisieren oder zufällige Entscheidungen zu treffen. Im Minisat werden beispielsweise zufällige Entscheidungen getroffen, indem eine Funktion aufgerufen wird, die bei Verwendung desselben zufälligen Startwerts immer dieselbe Zufallszahl zurückgibt. Wenn Sie also zu diesem Zeitpunkt keine Konfiguration des Solvers ändern, haben Sie immer die gleiche Antwort und das gleiche Modell. Das Ändern des zufälligen Startwerts hat beispielsweise keine Auswirkungen auf die Antwort (SAT oder UNSAT), kann jedoch das Modell und die Ausführungszeit ändern.
quelle