Ein vorläufiger Erfüllungsalgorithmus

  • Die allgemeine Erfüllbarkeit (mit einigen Ausnahmen wie Hornklauseln) gilt nicht als algorithmisch. Der folgende Algorithmus scheint jedoch eine Lösung für die allgemeine Erfüllbarkeit zu sein. Was genau ist der Fehler mit dem folgenden Algorithmus?

    1. Sei $ W $ eine leere Menge, die alle Variablen enthält, die notwendigerweise wahr oder falsch sein müssen.
    2. Sei $ L $ die Menge von Klauseln.
    3. Schleife durch $ L $.
    4. Jedes Mal, wenn eine nicht bedingte Variable † gefunden wird, entfernen Sie es aus $ L $ und fügen Sie es in $ W $ ein.
    5. Wenn dies eine leere AND-Auswirkung ergibt, entfernen Sie alle darin enthaltenen Variablen leere Implikation von $ L $ und Einfügen in $ W $.
    6. Wenn eine leere ODER-Implikation übrig bleibt, erstellen Sie neue Instanzen des Algorithmus, in denen sich jede Instanz befasst mit einer Variablen in der Implikation (dh wenn die Implikation lautet: $ x V \ impliziert y $), erstellen Sie eine Instanz, in der $ x $ in $ W $ eingefügt wird, eine, in der $ y $ in $ W $ eingefügt wird, und eine, in der $ steht x $ und $ y $ werden in $ W $) eingefügt.
    7. Setzen Sie alle Variablen in $ W $ auf den Wert, den sie unbedingt haben müssen.
    8. Setzen Sie die Variablen in $ W $ in $ L $ mit ihren geänderten Werten erneut ein und prüfen Sie, ob alle Klauseln erfüllt sind.
    9. Wenn Erfüllbarkeit erfüllt ist, geben Sie $ L $ zurück, andernfalls "Nicht zufriedenstellend".

    Eine nicht bedingte Variable ist als eine Variable definiert, die wahr oder falsch ist, z $ \ impliziert x $ oder $ \ impliziert \ neg y $.

    Eine leere Implikation wird als eine Implikation definiert, bei der eine Seite leer ist (z. B. $ \ impliziert x \ keil y $) oder die andere Seite ist notwendigerweise wahr (z. B. $ \ mathrm {true} \ vee a \ impliziert b $.

    Um intuitiver zu werden Um den Algorithmus zu verstehen, sollten Sie die folgenden Klauseln $ L $ berücksichtigen:

    $$ \ begin {align} a \ Wedge B & amp; \ impliziert c & amp; \ text {(i)} \\ & amp; \ impliziert f \ Wedge g & amp; \ text {(ii)} \\ f & amp; \ impliziert \ neg a & amp

    12 September 2012
    GillesTimeless
2 answers
  • Problem 1

    Der Fall $ (x \ rightarrow y \ vee \ overline y) $ sollte "nicht bedingt" sein Variable "in Bezug auf $ x $ (dh diese $ \ overline x $ sollte jetzt in $ W $ eingefügt werden). Wenn dies nicht der Fall ist, benötigt Ihr Algorithmus einen zusätzlichen Schritt, um dies abzuleiten. Unter der Annahme, dass $ (x \ rightarrow y \ vee \ overline y) $ eine " nicht bedingte Variable " ist, fahren wir fort.

    Problem 2

    HINWEIS: Dies ist ein Problem, das mir aufgefallen ist. Es kann durchaus andere Probleme geben.

    Das Problem ist mit der " leeren ODER-Implikation ", die in zwei Algorithmen aufgeteilt ist, nämlich die in ihrer aktuellen Form. Die Aufteilung deckt nicht alle Fälle ab. Insbesondere gilt:

    Sie beginnen mit $ (x \ vee c \ rightarrow y) $, dann wird $ c $ entfernt und es bleibt ein leeres ODER-Implikation < / em> von $ (x \ vee [] \ rightarrow y) $. Sie schlagen jetzt vor, es in zwei neue Probleme aufzuteilen und jedes davon zu lösen; einer mit $ x = T \ Wedge y = T $ und einer mit $ y = T $. Dies gilt jedoch nicht für alle Fälle. Was ist mit dem Fall, wenn $ x = F \ vee y = F $. Ihr Algorithmus zieht jedoch niemals die Möglichkeit in Betracht, dass $ y $ falsch ist.

    Ich denke, Sie könnten das Problem beheben, indem Sie die beiden neuen Probleme mit $ y $ und $ y $ formulieren Eins mit $ \ overline x $.

    Problem 3

    Was passiert, wenn Sie übrig bleiben eine Reihe von Klauseln in der Form:

    $$ (a \ wedge b \ rightarrow c) $$

    oder

    $$ (a \ rightarrow b \ vee c) $$

    Nachdem Sie alles reduziert haben, bleiben diese Klauseln erhalten, und Sie haben gewonnen. Ihre Erfüllbarkeit kann leicht getestet werden.

    Analyse

    Hinweis : Diese "O" -Notation, $ \ mathcal {O} (etwas) $ usw., wird als Big bezeichnet O-Notation . $ \ Omega (etwas) $ heißt Big-Omega.

    Angenommen, der Algorithmus funktionierte im Allgemeinen, würde er in der Zeit laufen

    19 September 2012
    Jay Corbett
  • Bevor Sie das Gefühl haben, dass Sie einen "neuen" SAT-Algorithmus haben, lesen Sie bitte den Standard- / klassischen Backtracking- / Suchalgorithmus in der Literatur für das Problem, das auf ~ 1962 datiert, das Davis-Putnam-Logemann-Loveland-Algorithmus . Die meisten Rückverfolgungs- / Rekursionsalgorithmen für das Problem werden wahrscheinlich diesem Algorithmus etwas ähneln, obwohl es einige Zeit dauern kann, um diese Äquivalenz zu demonstrieren.

    Für eine seriöse Analyse ist ein Benchmarking erforderlich Algorithmus gegen Beispiele (oder zufällige Instanzen) vs. DPLL.

    Daher ist es hilfreich, nur zusammenzufassen, wie sich Ihr Algorithmus davon unterscheidet. Ohne den Code zu überprüfen, sind die Quoten:

    • Der Algorithmus enthält einen Fehler. entweder False Positive oder Negative zurückgeben (dh der Algorithmus gibt "Formel ist zufriedenstellend" zurück, wenn dies nicht der Fall ist oder umgekehrt). Dies kann in der Regel durch sehr gründliches Testen einer großen Anzahl von zufällig generierten Formeln und durch Überprüfen auf einen anderen bekannten korrekten Algorithmus / Implementierung , z. B. DPLL, festgestellt werden.
    • Ihr Algorithmus ist dies nicht So gut wie DPLL.
    • Wenn es genauso gut wie DPLL oder "besser" ist, liegt es im Allgemeinen an Heuristiken / Strategien für Verzweigungs- und Variablenauswahl sowie an der Verteilung der getesteten Instanzen.

    Der Algorithmus kann von einem intelligenten Student leicht verstanden werden, er scheint jedoch selten auf der Ebene des Undergraduate oder in Undergraduate-Lehrbüchern gelehrt zu werden, oder wird möglicherweise nicht einmal häufig referenziert zu einer falschen Ansicht oder dem Eindruck, dass grundlegende SAT-Algorithmen nicht gut verstanden werden usw.

    Kürzlich stieß ich gerade auf dieser "Live" -Seite mit dem Namen ToughSat von Yuen und Bebel zur Erzeugung harter Instanzen für Benchmarking, einige basieren auf Factoring [eines der klassischen SAT-Hard-Ins tanzgenerierungsmethoden]. es gibt andere zB

    06 September 2015
    Sergey Skoblikov