Boolesches Erfüllbarkeitsproblem - Boolean satisfiability problem

In der Logik und Informatik ist das Boolesche Erfüllbarkeitsproblem (manchmal auch propositionales Erfüllbarkeitsproblem genannt und abgekürzt SATISFIABILITY , SAT oder B-SAT ) das Problem zu bestimmen, ob es eine Interpretation gibt , die eine gegebene Boolesche Formel erfüllt . Mit anderen Worten, es fragt, ob die Variablen einer gegebenen booleschen Formel konsistent durch die Werte TRUE oder FALSE ersetzt werden können, so dass die Formel TRUE ergibt . Ist dies der Fall, heißt die Formel erfüllbar. Auf der anderen Seite, wenn keine solche Zuordnung vorhanden ist , wird die Funktion durch die Formel ausgedrückt ist FALSCH für alle möglichen Variablenzuweisungen und die Formel unerfüllbar . Zum Beispiel ist die Formel " a AND NOT b " erfüllbar, weil man die Werte a  = WAHR und b  = FALSE finden kann, die ( a AND NOT b ) = WAHR machen. Im Gegensatz dazu ist " a AND NOT a " unerfüllbar.

SAT ist das erste Problem, das sich als NP-vollständig erwiesen hat ; siehe Cook-Levin-Theorem . Dies bedeutet, dass alle Probleme der Komplexitätsklasse NP , die eine Vielzahl natürlicher Entscheidungs- und Optimierungsprobleme umfasst, höchstens so schwer zu lösen sind wie SAT. Es gibt keinen bekannten Algorithmus, der jedes SAT-Problem effizient löst, und es wird allgemein angenommen, dass kein solcher Algorithmus existiert; diese Annahme ist jedoch mathematisch nicht bewiesen, und die Lösung der Frage, ob SAT einen Polynomialzeitalgorithmus hat, entspricht dem P-gegen-NP-Problem , einem berühmten offenen Problem in der Computertheorie.

Trotzdem können heuristische SAT-Algorithmen seit 2007 Problemfälle mit Zehntausenden von Variablen und Formeln mit Millionen von Symbolen lösen, was für viele praktische SAT-Probleme aus zB künstlicher Intelligenz , Schaltungsdesign und Automatik ausreichend ist Satz beweisen .

Grundlegende Definitionen und Terminologie

Eine aussagenlogische Formel , auch Boolescher Ausdruck genannt , besteht aus Variablen , Operatoren UND ( Konjunktion , auch mit ∧ bezeichnet), ODER ( Disjunktion , ∨), NICHT ( Negation , ¬) und Klammern. Eine Formel wird als erfüllbar bezeichnet, wenn sie WAHR gemacht werden kann, indem ihren Variablen entsprechende logische Werte (dh WAHR, FALSCH) zugewiesen werden. Das Boolesche Erfüllbarkeitsproblem (SAT) ist eine Formel gegeben, um zu überprüfen, ob es erfüllbar ist. Dieses Entscheidungsproblem ist in vielen Bereichen der Informatik von zentraler Bedeutung , darunter Theoretische Informatik , Komplexitätstheorie , Algorithmik , Kryptographie und Künstliche Intelligenz .

Es gibt mehrere Spezialfälle des Booleschen Erfüllbarkeitsproblems, in denen die Formeln eine bestimmte Struktur haben müssen. Ein Literal ist entweder eine Variable, die als positives Literal bezeichnet wird , oder die Negation einer Variablen, die als negatives Literal bezeichnet wird . Eine Klausel ist eine Disjunktion von Literalen (oder ein einzelnes Literal). Eine Klausel heißt Horn-Klausel, wenn sie höchstens ein positives Literal enthält. Eine Formel liegt in konjunktiver Normalform (CNF) vor, wenn sie eine Konjunktion von Klauseln (oder eine einzelne Klausel) ist. Zum Beispiel ist x 1 ein positives Literal, ¬ x 2 ist ein negatives Literal, x 1 ∨ ¬ x 2 ist eine Klausel. Die Formel ( x 1 ∨ ¬ x 2 ) ∧ (¬ x 1x 2x 3 ) ∧ ¬ x 1 ist in konjunktiver Normalform; sein erster und dritter Satz sind Hornsätze, sein zweiter Satz jedoch nicht. Die Formel ist erfüllbar, indem x 1  = FALSE, x 2  = FALSE und x 3 willkürlich gewählt wird, denn (FALSE ¬FALSE) ∧ (¬FALSE ∨ FALSE ∨ x 3 ) ∧ ¬FALSE ergibt (FALSE ∨ TRUE) ∧ (WAHR ∨ FALSE ∨ x 3 ) WAHR, und wiederum auf WAHR ∧ WAHR ∧ WAHR (dh auf WAHR). Im Gegensatz dazu ist die CNF-Formel a ¬ ¬ a , die aus zwei Klauseln eines Literals besteht, unerfüllbar, da sie für a =TRUE oder a =FALSE zu TRUE ∧ ¬TRUE (dh FALSE) oder FALSE ∧ ¬FALSE (dh , wieder FALSCH) bzw.

Für einige Versionen des SAT-Problems ist es nützlich, den Begriff einer verallgemeinerten konjunktiven Normalformformel zu definieren , nämlich. als Konjunktion beliebig vieler generalisierter Klauseln , wobei letztere die Form R ( l 1 ,..., l n ) für eine Boolesche Funktion R und (gewöhnliche) Literale l i haben . Unterschiedliche Sätze zulässiger boolescher Funktionen führen zu unterschiedlichen Problemversionen. Als Beispiel ist Rx , a , b ) eine verallgemeinerte Klausel und Rx , a , b ) ∧ R ( b , y , c ) ∧ R ( c , d , ¬ z ) ist eine verallgemeinerte konjunktive Normalform. Diese Formel wird unten verwendet , wobei R der ternäre Operator ist, der genau dann WAHR ist, wenn genau eines seiner Argumente ist.

Mit den Gesetzen der Booleschen Algebra lässt sich jede aussagenlogische Formel in eine äquivalente konjunktive Normalform überführen, die jedoch exponentiell länger sein kann. Transformiert man beispielsweise die Formel ( x 1y 1 ) ∨ ( x 2y 2 ) ∨ ... ∨ ( x ny n ) in die konjunktive Normalform

( x 1  ∨  x 2  ∨ … ∨  x n ) ∧
( y 1  ∨  x 2  ∨ … ∨  x n ) ∧
( x 1  ∨  y 2  ∨ … ∨  x n ) ∧
( y 1  ∨  y 2  ∨ … ∨  x n ) ∧ ... ∧
( x 1  ∨  x 2  ∨ … ∨  y n ) ∧
( y 1  ∨  x 2  ∨ … ∨  y n ) ∧
( x 1  ∨  y 2  ∨ … ∨  y n ) ∧
( y 1  ∨  y 2  ∨ … ∨  y n ) ;

während erstere eine Disjunktion von n Konjunktionen von 2 Variablen ist, besteht letztere aus 2 n Klauseln von n Variablen.

Komplexität und eingeschränkte Versionen

Uneingeschränkte Erfüllbarkeit (SAT)

SAT war das erste bekannte NP-vollständige Problem, das 1971 von Stephen Cook an der University of Toronto und 1973 unabhängig von Leonid Levin an der National Academy of Sciences bewiesen wurde . Bis dahin war das Konzept eines NP-vollständigen Problems nicht bekannt sogar existieren. Der Beweis zeigt , wie jedes Entscheidungsproblem in der Komplexitätsklasse NP kann reduziert für CNF Formeln an das SAT Problem, manchmal genannt CNFSAT . Eine nützliche Eigenschaft von Cooks Reduktion besteht darin, dass sie die Anzahl der akzeptierenden Antworten beibehält. Zum Beispiel ist die Entscheidung, ob ein gegebener Graph eine 3-Färbung hat, ein weiteres Problem in NP; Wenn ein Graph 17 gültige 3-Färbungen hat, hat die SAT-Formel, die durch die Cook-Levin-Reduktion erzeugt wird, 17 befriedigende Zuordnungen.

NP-Vollständigkeit bezieht sich nur auf die Laufzeit der Worst-Case-Instanzen. Viele der in der Praxis vorkommenden Fälle lassen sich viel schneller lösen. Siehe Algorithmen zur Lösung von SAT weiter unten.

SAT ist trivial, wenn die Formeln auf diejenigen in disjunktiver Normalform beschränkt sind , also eine Disjunktion von Konjunktionen von Literalen sind. Eine solche Formel ist in der Tat genau dann erfüllbar, wenn mindestens eine ihrer Konjunktionen erfüllbar ist, und eine Konjunktion ist genau dann erfüllbar, wenn sie nicht sowohl x als auch NICHT x für eine Variable x enthält . Dies kann in linearer Zeit überprüft werden. Wenn sie außerdem darauf beschränkt sind, in vollständig disjunktiver Normalform zu sein , in der jede Variable in jeder Konjunktion genau einmal vorkommt, können sie in konstanter Zeit überprüft werden (jede Konjunktion stellt eine befriedigende Zuweisung dar). Es kann jedoch exponentiell Zeit und Raum in Anspruch nehmen, ein allgemeines SAT-Problem in eine disjunktive Normalform umzuwandeln; für ein Beispiel tauschen Sie "∧" und "∨" im obigen exponentiellen Blow-up-Beispiel für konjunktive Normalformen aus.

3-Erfüllbarkeit

Die 3-SAT - Instanz ( xxy ) ∧ (¬ x ∨ ¬ y ∨ ¬ y ) ∧ (¬ xyy ) auf eine reduzierte Clique Problem . Die grünen Eckpunkte bilden eine 3-Clique und entsprechen der erfüllenden Zuweisung x = FALSE, y = TRUE.

Wie das Erfüllbarkeitsproblem für beliebige Formeln ist auch die Bestimmung der Erfüllbarkeit einer Formel in konjunktiver Normalform, bei der jede Klausel auf höchstens drei Literale beschränkt ist, NP-vollständig; dieses Problem wird 3-SAT , 3CNFSAT oder 3-Erfüllbarkeit genannt . Um das uneingeschränkte SAT-Problem auf 3-SAT zu reduzieren, transformiere jede Klausel l 1 ∨ ⋯ ∨ l n in eine Konjunktion von n - 2 Klauseln

( l 1l 2x 2 )
x 2l 3x 3 ) ∧
x 3l 4x 4 ) ∧ ⋯ ∧
x n − 3l n − 2x n − 2 ) ∧
x n − 2l n − 1l n )

wobei x 2 , ⋯ ,  x n − 2 neue Variablen sind, die anderswo nicht vorkommen. Obwohl die beiden Formeln logisch nicht äquivalent sind , sind sie gleich erfüllbar . Die aus der Transformation aller Klauseln resultierende Formel ist höchstens dreimal so lang wie ihr Original, dh das Längenwachstum ist polynomiell.

3-SAT ist eines der 21 NP-vollständigen Probleme von Karp und wird als Ausgangspunkt für den Beweis verwendet, dass auch andere Probleme NP-schwer sind . Dies geschieht durch polynomielle Zeitreduktion von 3-SAT auf das andere Problem. Ein Beispiel für ein Problem, bei dem diese Methode verwendet wurde, ist das Cliquenproblem : Wenn eine CNF-Formel aus c Klauseln besteht, besteht der entsprechende Graph aus einem Scheitelpunkt für jedes Literal und einer Kante zwischen jeweils zwei nicht widersprüchlichen Literalen aus verschiedenen Klauseln, vgl. Bild. Der Graph hat genau dann eine c -Clique, wenn die Formel erfüllbar ist.

Es gibt einen einfachen randomisierten Algorithmus nach Schöning (1999), der in der Zeit (4/3) n läuft, wobei n die Anzahl der Variablen in der 3-SAT-Proposition ist und mit hoher Wahrscheinlichkeit 3-SAT richtig entscheidet.

Die exponentielle Zeithypothese behauptet, dass kein Algorithmus 3-SAT (oder tatsächlich k- SAT für jeden ) in exp( o ( n ))- Zeit (dh grundsätzlich schneller als exponentiell in n ) lösen kann .

Selman, Mitchell und Levesque (1996) geben empirische Daten zur Schwierigkeit zufällig generierter 3-SAT-Formeln in Abhängigkeit von ihren Größenparametern. Die Schwierigkeit wird in zahlenrekursiven Anrufen gemessen, die von einem DPLL-Algorithmus ausgeführt werden .

3-Erfüllbarkeit kann zu k-Erfüllbarkeit ( k-SAT , auch k-CNF-SAT ) verallgemeinert werden , wenn Formeln in CNF betrachtet werden, wobei jede Klausel bis zu k Literale enthält. Da jedoch für jedes k 3 dieses Problem weder einfacher als 3-SAT noch schwieriger als SAT sein kann und die beiden letzteren NP-vollständig sind, muss auch k-SAT sein.

Einige Autoren beschränken k-SAT auf CNF-Formeln mit genau k Literalen . Dies führt auch nicht zu einer anderen Komplexitätsklasse, da jede Klausel l 1 ∨ ⋯ ∨ l j mit j < k Literalen mit festen Dummy-Variablen aufgefüllt werden kann auf l 1 ∨ ⋯ ∨ l jd j +1 ∨ ⋯ ∨ d k . Nach dem Auffüllen aller Klauseln müssen 2 k -1 zusätzliche Klauseln angehängt werden, um sicherzustellen, dass nur d 1 = ⋯ = d k = FALSE zu einer befriedigenden Zuweisung führen kann. Da k nicht von der Formellänge abhängt, führen die zusätzlichen Klauseln zu einer konstanten Längenzunahme. Aus dem gleichen Grund spielt es keine Rolle, ob doppelte Literale in Klauseln erlaubt sind, wie in ¬ x ∨ ¬ y ∨ ¬ y .

Exakt-1 3-Erfüllbarkeit

Links: Schäfers Reduktion einer 3-SAT-Klausel xyz . Das Ergebnis von R ist TRUE (1), wenn genau eines seiner Argumente TRUE ist, andernfalls FALSE (0) . Alle 8 Kombinationen von Werten für x , y , z werden untersucht, eine pro Zeile. Die frischen Variablen a , ..., f können alle Klauseln erfüllen gewählt werden (genau ein grünes Argument für jedes R ) in allen Zeilen mit Ausnahme des ersten, in der xyz FALSE ist. Rechts: Eine einfachere Reduktion mit den gleichen Eigenschaften.

Eine Variante des 3-Erfüllbarkeitsproblems ist das eins-in-drei 3-SAT (auch verschieden als 1-in-3-SAT und genau-1 3-SAT bekannt ). Bei einer konjunktiven Normalform mit drei Literalen pro Klausel besteht das Problem darin, festzustellen, ob den Variablen eine Wahrheitszuweisung vorliegt, so dass jede Klausel genau ein WAHR-Literal (und damit genau zwei FALSCH-Literale) hat. Im Gegensatz dazu erfordert gewöhnliches 3-SAT, dass jede Klausel mindestens ein TRUE-Literal enthält. Formal wird ein eins-zu-drei 3-SAT-Problem als verallgemeinerte konjunktive Normalform mit allen verallgemeinerten Klauseln unter Verwendung eines ternären Operators R gegeben , der genau dann WAHR ist, wenn genau eines seiner Argumente WAHR ist. Wenn alle Literale einer eins-in-drei 3-SAT-Formel positiv sind, wird das Erfüllbarkeitsproblem als eins-in-drei positives 3-SAT bezeichnet .

One-in-three 3-SAT, zusammen mit seinem positiven Fall, wird in der Standardreferenz Computers and Intractability: A Guide to the Theory of NP-Completeness von Michael R. Garey und David als NP-vollständiges Problem "LO4" aufgeführt S. Johnson . Eins-zu-drei 3-SAT wurde von Thomas Jerome Schaefer als Spezialfall des Dichotomie-Theorems von Schaefer als NP-vollständig bewiesen , der behauptet, dass jedes Problem, das die Boolesche Erfüllbarkeit auf eine bestimmte Weise verallgemeinert, entweder in der Klasse P liegt oder NP- Komplett.

Schaefer liefert eine Konstruktion, die eine einfache Polynomialzeitreduktion von 3-SAT auf eins-in-drei 3-SAT ermöglicht. Sei "( x oder y oder z )" eine Klausel in einer 3CNF-Formel. Fügen Sie sechs neue boolesche Variablen a , b , c , d , e und f hinzu , um diese Klausel und keine andere zu simulieren. Dann ist die Formel R ( x , a , d ) R ( y , b , d ) ∧ R ( a , b , e ) ∧ R ( c , d , f ) ∧ R ( z , c , FALSE ) erfüllbar durch einige Einstellungen der frischen Variablen nur dann, wenn mindestens eines von x , y oder z WAHR ist, siehe Bild (links). Somit kann jede 3-SAT-Instanz mit m Klauseln und n Variablen in eine gleicherfüllbare eins-zu-drei 3-SAT-Instanz mit 5 m Klauseln und n +6 m Variablen umgewandelt werden. Eine weitere Reduktion beinhaltet nur vier neue Variablen und drei Klauseln: Rx , a , b ) R ( b , y , c ) ∧ R( c , dz ), siehe Bild (rechts).

Nicht-alles-gleich 3-Erfüllbarkeit

Eine weitere Variante ist das Not-all-Equal 3-Erfüllbarkeitsproblem (auch NAE3SAT genannt ). Bei einer konjunktiven Normalform mit drei Literalen pro Klausel besteht das Problem darin, festzustellen, ob eine Zuweisung an die Variablen existiert, so dass in keiner Klausel alle drei Literale denselben Wahrheitswert haben. Auch dieses Problem ist nach dem Dichotomiesatz von Schaefer NP-vollständig, selbst wenn keine Negationssymbole zugelassen sind.

Linearer SAT

Eine 3-SAT-Formel ist Linear SAT ( LSAT ), wenn jede Klausel (betrachtet als eine Menge von Literalen) höchstens eine andere Klausel schneidet, und wenn sich außerdem zwei Klauseln schneiden, dann haben sie genau ein Literal gemeinsam. Eine LSAT-Formel kann als eine Menge von disjunkten halbgeschlossenen Intervallen auf einer Linie dargestellt werden. Die Entscheidung, ob eine LSAT-Formel erfüllbar ist oder nicht, ist NP-vollständig.

2-Erfüllbarkeit

SAT ist einfacher, wenn die Anzahl der Literale in einer Klausel auf höchstens 2 beschränkt ist. In diesem Fall heißt das Problem 2-SAT . Dieses Problem kann in polynomieller Zeit gelöst werden und ist für die Komplexitätsklasse NL tatsächlich vollständig . Wenn zusätzlich alle ODER-Verknüpfungen in Literalen in XOR- Verknüpfungen umgewandelt werden, heißt das Ergebnis Exklusiv-Oder 2-Erfüllbarkeit , was für die Komplexitätsklasse SL = L ein Problem vollständig ist .

Horn-Erfüllbarkeit

Das Problem der Entscheidung über die Erfüllbarkeit einer gegebenen Konjunktion von Horn-Klauseln wird Horn-Erfüllbarkeit oder HORN-SAT genannt . Sie kann in polynomieller Zeit durch einen einzigen Schritt des Einheitspropagationsalgorithmus gelöst werden, der das einzelne minimale Modell der Menge der Horn-Klauseln (bezogen auf die Menge der Literalen, die WAHR zugewiesen sind) erzeugt. Die Hornerfüllbarkeit ist P-vollständig . Es kann als Ps Version des Booleschen Erfüllbarkeitsproblems angesehen werden. Auch die Entscheidung über die Wahrheit quantifizierter Horn-Formeln kann in polynomieller Zeit erfolgen.

Horn-Klauseln sind von Interesse, weil sie die Implikation einer Variablen aus einer Menge anderer Variablen ausdrücken können. Tatsächlich kann eine solche Klausel ¬ x 1 ∨ ... ∨ ¬ x ny umgeschrieben werden als x 1 ∧ ... ∧ x ny , dh wenn x 1 ,..., x n alle WAHR sind , dann muss auch y TRUE sein.

Eine Verallgemeinerung der Klasse von Horn-Formeln ist die der umbenennbaren Horn-Formeln, die der Satz von Formeln ist, die in Horn-Form platziert werden können, indem einige Variablen durch ihre jeweilige Negation ersetzt werden. Zum Beispiel ( x 1 ∨ ¬ x 2 ) ∧ (¬ x 1x 2x 3 ) ∧ ¬ x 1 ist keine Hornformel, kann aber in die Hornformel umbenannt werden ( x 1 ∨ ¬ x 2 ) ∧ (¬ x 1x 2 ∨ ¬ y 3 ) ∧ ¬ x 1 durch Einführung von y 3 als Negation von x 3 . Dagegen führt keine Umbenennung von ( x 1 ¬ x 2 ∨ ¬ x 3 ) ∧ (¬ x 1x 2x 3 ) ¬ x 1 zu einer Horn-Formel. Die Überprüfung der Existenz eines solchen Ersatzes kann in linearer Zeit erfolgen; daher liegt die Erfüllbarkeit solcher Formeln in P, da sie gelöst werden kann, indem zuerst diese Ersetzung durchgeführt und dann die Erfüllbarkeit der resultierenden Horn-Formel überprüft wird.

Eine Formel mit 2 Klauseln kann je nach TRUE-Literalzahl in der 1. (hor) und 2. (vert) Satz.

XOR-Erfüllbarkeit

Ein weiterer Spezialfall ist die Klasse von Problemen, bei denen jede Klausel XOR (dh exklusives oder ) anstelle von (einfachen) ODER-Operatoren enthält. Dies ist in P , da eine XOR-SAT-Formel auch als lineares Gleichungssystem mod 2 angesehen werden kann und in kubischer Zeit durch Gaußsche Elimination gelöst werden kann ; ein Beispiel finden Sie in der Box. Diese Neufassung basiert auf der Verwandtschaft zwischen Booleschen Algebren und Booleschen Ringen und der Tatsache, dass Arithmetik Modulo Zwei einen endlichen Körper bildet . Da ein XOR b XOR c genau dann WAHR wird, wenn genau 1 oder 3 Mitglieder von { a , b , c } WAHR sind, ist jede Lösung des 1-in-3-SAT-Problems für eine gegebene CNF-Formel auch eine Lösung des XOR-3-SAT-Problems, und jede Lösung von XOR-3-SAT ist wiederum eine Lösung von 3-SAT, vgl. Bild. Folglich ist es für jede CNF-Formel möglich, das durch die Formel definierte XOR-3-SAT-Problem zu lösen und basierend auf dem Ergebnis zu folgern, dass entweder das 3-SAT-Problem lösbar ist oder dass das 1-in-3- SAT-Problem ist unlösbar.

Sofern die Komplexitätsklassen P und NP nicht gleich sind , ist im Gegensatz zu SAT weder 2-, noch Horn-, noch XOR-Erfüllbarkeit NP-vollständig.

Dichotomie-Theorem von Schäfer

Die obigen Einschränkungen (CNF, 2CNF, 3CNF, Horn, XOR-SAT) haben die betrachteten Formeln als Konjunktionen von Teilformeln gebunden; jede Einschränkung gibt eine spezifische Form für alle Teilformeln an: zum Beispiel können in 2CNF nur binäre Klauseln Teilformeln sein.

Der Dichotomiesatz von Schaefer besagt, dass für jede Einschränkung auf Boolesche Funktionen, die zur Bildung dieser Teilformeln verwendet werden können, das entsprechende Erfüllbarkeitsproblem P- oder NP-vollständig ist. Die Zugehörigkeit der Erfüllbarkeit von 2CNF-, Horn- und XOR-SAT-Formeln in P sind Spezialfälle dieses Theorems.

Die folgende Tabelle fasst einige gängige Varianten von SAT zusammen.

Code Name Einschränkungen Anforderungen Klasse
3SAT 3-Erfüllbarkeit Jede Klausel enthält 3 Literale. Mindestens ein Literal muss wahr sein. NPC
2SAT 2-Erfüllbarkeit Jede Klausel enthält 2 Literale. Mindestens ein Literal muss wahr sein. P
1-in-3-SAT Genau-1 3-SAT Jede Klausel enthält 3 Literale. Genau ein Literal muss wahr sein. NPC
1-in-3-SAT+ Genau 1 positives 3-SAT Jede Klausel enthält 3 positive Literale. Genau ein Literal muss wahr sein. NPC
NAE3SAT Nicht-alles-gleich 3-Erfüllbarkeit Jede Klausel enthält 3 Literale. Entweder ein oder zwei Literale müssen wahr sein. NPC
NAE3SAT+ Nicht alle gleich positive 3-SAT Jede Klausel enthält 3 positive Literale. Entweder ein oder zwei Literale müssen wahr sein. NPC
PL-SAT Planar SAT Der Inzidenzgraph (Klausel-Variablen-Graph) ist planar . Mindestens ein Literal muss wahr sein. NPC
L3SAT Linear 3-SAT Jede Klausel schneidet höchstens eine andere Klausel, und die Schnittmenge ist genau ein Literal. Mindestens ein Literal muss wahr sein. NPC
HORN-SAT Hornerfüllbarkeit Hornsätze (höchstens ein positives Literal). Mindestens ein Literal muss wahr sein. P
XOR-SAT Xor Erfüllbarkeit Jede Klausel enthält XOR-Operationen statt OR. Das XOR aller Literale muss wahr sein. P

Erweiterungen von SAT

Eine Erweiterung, die seit 2003 erhebliche Popularität gewonnen hat , ist die Erfüllbarkeit Modulo Theorien ( SMT ) , die CNF Formeln mit linearen Bedingungen bereichern kann, Arrays, all-verschiedene Einschränkungen, nicht interpretierten Funktionen , usw. Solche Erweiterungen der Regel bleiben NP-vollständig, aber sehr effiziente Solver sind jetzt verfügbar, die viele dieser Arten von Einschränkungen handhaben kann.

Das Erfüllbarkeitsproblem wird schwieriger, wenn sowohl "für alle" ( ) als auch "es existiert" ( ) Quantoren die Booleschen Variablen binden dürfen. Ein Beispiel für eine solche Expression wäre xyz ( xyz ) ∧ (¬ x ∨ ¬ y ∨ ¬ z ) ; es ist gültig, da für alle Werte von x und y ein geeigneter Wert von z gefunden werden kann, nämlich. z = TRUE, wenn sowohl x als auch y FALSE sind, andernfalls z = FALSE. SAT selbst verwendet (stillschweigend) nur ∃-Quantoren. Wenn nur ∀ quantifiers stattdessen erlaubt, die so genannte Tautologie Problem erhalten, das ist co-NP-vollständig . Wenn beide Quantoren zugelassen sind, wird das Problem als quantifiziertes Boolesches Formelproblem ( QBF ) bezeichnet, das als PSPACE-vollständig gezeigt werden kann . Es wird allgemein angenommen, dass PSPACE-vollständige Probleme strenger sind als jedes Problem in NP, obwohl dies noch nicht bewiesen wurde. Mit hochparallelen P-Systemen können QBF-SAT-Probleme in linearer Zeit gelöst werden.

Gewöhnlicher SAT fragt, ob es mindestens eine Variablenzuweisung gibt, die die Formel wahr macht. Eine Vielzahl von Varianten befassen sich mit der Anzahl solcher Zuordnungen:

  • MAJ-SAT fragt, ob die Mehrheit aller Zuordnungen die Formel WAHR macht. Es ist bekannt, dass sie für PP , eine probabilistische Klasse , vollständig ist .
  • #SAT , das Problem zu zählen, wie viele Variablenzuweisungen eine Formel erfüllen, ist ein Zählproblem , kein Entscheidungsproblem und #P-vollständig .
  • UNIQUE SAT ist das Problem festzustellen, ob eine Formel genau eine Zuordnung hat. Es ist vollständig für US , die Komplexitätsklasse, die Probleme beschreibt, die durch eine nicht-deterministische polynomiale Zeit- Turingmaschine lösbar sind , die akzeptiert, wenn es genau einen nicht-deterministischen akzeptierenden Pfad gibt, und anderenfalls ablehnt.
  • EINDEUTIGE-SAT ist der Name für das Erfüllbarkeitsproblem gegeben , wenn der Eingang ist beschränkt auf die Formeln mit höchstens eine erfüllende Aufgabe. Das Problem wird auch USAT genannt . Ein Lösungsalgorithmus für UNAMBIGUOUS-SAT darf bei einer Formel mit mehreren zufriedenstellenden Zuweisungen jedes Verhalten zeigen, einschließlich Endlosschleifen. Obwohl dieses Problem einfacher erscheint, haben Valiant und Vazirani gezeigt, dass alle Probleme in NP genauso leicht gelöst werden können , wenn es einen praktikablen (dh randomisierten Polynomialzeit- ) Algorithmus gibt, um es zu lösen.
  • MAX-SAT , das maximale Erfüllbarkeitsproblem , ist eine FNP- Verallgemeinerung von SAT. Es fragt nach der maximalen Anzahl von Klauseln, die durch eine Zuweisung erfüllt werden können. Es hat effiziente Approximationsalgorithmen , ist aber NP-schwer exakt zu lösen. Schlimmer noch, es ist APX- vollständig, was bedeutet, dass es kein Polynomial-Time-Approximation-Schema (PTAS) für dieses Problem gibt, es sei denn, P = NP.
  • WMSAT ist das Problem, eine Zuweisung mit minimalem Gewicht zu finden, die einer monotonen Booleschen Formel (dh einer Formel ohne Negation) genügt. Gewichte von Aussagenvariablen werden in der Eingabe des Problems angegeben. Die Gewichtung einer Zuweisung ist die Summe der Gewichtungen der wahren Variablen. Dieses Problem ist NP-vollständig (siehe Th. 1 von ).

Andere Verallgemeinerungen umfassen Erfüllbarkeit für Logik erster und zweiter Ordnung , Probleme der Erfüllung von Beschränkungen , 0-1 Integer-Programmierung .

Selbstreduzierbarkeit

Das SAT-Problem ist selbstreduzierbar , d. h. jeder Algorithmus, der richtig antwortet, wenn eine Instanz von SAT lösbar ist, kann verwendet werden, um eine befriedigende Aufgabe zu finden. Zunächst wird die Frage nach der gegebenen Formel Φ gestellt. Wenn die Antwort "nein" lautet, ist die Formel nicht erfüllbar. Andernfalls wird die Frage nach der teilweise instanziierten Formel Φ { x 1 =TRUE} , dh Φ mit der ersten Variablen x 1 durch WAHR ersetzt, gestellt und entsprechend vereinfacht. Wenn die Antwort "ja" ist, dann ist x 1 = WAHR, andernfalls x 1 = FALSCH. Werte anderer Variablen können anschließend auf die gleiche Weise gefunden werden. Insgesamt sind n +1 Durchläufe des Algorithmus erforderlich, wobei n die Anzahl der verschiedenen Variablen in ist.

Diese Eigenschaft der Selbstreduzierbarkeit wird in mehreren Theoremen der Komplexitätstheorie verwendet:

NPP/polyPH = Σ 2   ( Satz von Karp-Lipton )
NPBPPNP = RP
P = NPFP = FNP

Algorithmen zur Lösung von SAT

Da das SAT-Problem NP-vollständig ist, sind dafür nur Algorithmen mit exponentieller Worst-Case-Komplexität bekannt. Trotzdem wurden in den 2000er Jahren effiziente und skalierbare Algorithmen für SAT entwickelt und haben zu dramatischen Fortschritten in unserer Fähigkeit beigetragen, Probleminstanzen mit Zehntausenden von Variablen und Millionen von Einschränkungen (dh Klauseln) automatisch zu lösen. Beispiele für solche Probleme in der Electronic Design Automation (EDA) umfassen formale Äquivalenzprüfung , Modellprüfung , formale Verifikation von Pipeline-Mikroprozessoren , automatische Testmustererzeugung , Routing von FPGAs , Planungs- und Scheduling-Probleme und so weiter. Eine SAT-Lösungsmaschine gilt heute als wesentlicher Bestandteil der EDA- Toolbox.

Ein DPLL-SAT-Solver verwendet ein systematisches Backtracking-Suchverfahren, um den (exponentiell großen) Raum von Variablenzuweisungen auf der Suche nach zufriedenstellenden Zuweisungen zu untersuchen. Das grundlegende Suchverfahren wurde in den frühen 1960er Jahren in zwei bahnbrechenden Arbeiten vorgeschlagen (siehe Referenzen unten) und wird heute allgemein als Davis-Putnam-Logemann-Loveland-Algorithmus ("DPLL" oder "DLL") bezeichnet. Viele moderne Ansätze zur praktischen SAT-Lösung werden vom DPLL-Algorithmus abgeleitet und haben dieselbe Struktur. Oftmals verbessern sie nur die Effizienz bestimmter Klassen von SAT-Problemen wie Instanzen, die in industriellen Anwendungen vorkommen oder zufällig generierte Instanzen. Theoretisch wurden exponentielle untere Schranken für die DPLL-Familie von Algorithmen bewiesen.

Algorithmen, die nicht zur DPLL-Familie gehören, umfassen stochastische lokale Suchalgorithmen. Ein Beispiel ist WalkSAT . Stochastische Methoden versuchen, eine zufriedenstellende Interpretation zu finden, können aber nicht ableiten, dass eine SAT-Instanz im Gegensatz zu vollständigen Algorithmen wie DPLL unerfüllbar ist.

Im Gegensatz dazu setzen randomisierte Algorithmen wie der PPSZ-Algorithmus von Paturi, Pudlak, Saks und Zane Variablen in einer zufälligen Reihenfolge gemäß einigen Heuristiken, zum Beispiel Auflösung mit begrenzter Breite . Wenn die Heuristik nicht die richtige Einstellung findet, wird die Variable zufällig zugewiesen. Der PPSZ-Algorithmus hat eine Laufzeit von für 3-SAT. Dies war die bekannteste Laufzeit für dieses Problem bis zu einer kürzlichen Verbesserung von Hansen, Kaplan, Zamir und Zwick, die eine Laufzeit von 3-SAT und derzeit die bekannteste Laufzeit für k-SAT für alle Werte von k hat. Im Setting mit vielen zufriedenstellenden Zuweisungen hat der randomisierte Algorithmus von Schöning eine bessere Schranke.

Moderne SAT-Solver (entwickelt in den 2000er Jahren) gibt es in zwei Varianten: "konfliktgesteuert" und "vorausschauend". Beide Ansätze stammen von DPLL ab. Konfliktgesteuerte Solver, wie z. B. Conflict-Driven Clause Learning (CDCL), erweitern den grundlegenden DPLL-Suchalgorithmus um effiziente Konfliktanalyse, Klausellernen , nicht- chronologisches Backtracking (auch Backjumping genannt ) sowie „Two- Watched -Literals“-Einheit Propagation , adaptive Verzweigung und zufällige Neustarts. Diese "Extras" zur grundlegenden systematischen Suche haben sich empirisch als wesentlich für den Umgang mit den großen SAT-Instanzen erwiesen, die in der Electronic Design Automation (EDA) auftreten. Bekannte Implementierungen umfassen Chaff und GRASP . Look-Ahead-Solver haben insbesondere die Reduktionen (die über die Propagierung von Einheitsklauseln hinausgehen) und die Heuristik verstärkt, und sie sind im Allgemeinen stärker als konfliktgesteuerte Solver auf harten Instanzen (während konfliktgesteuerte Solver bei großen Instanzen viel besser sein können, die tatsächlich eine einfache Instanz im Inneren).

Moderne SAT-Solver haben unter anderem auch erhebliche Auswirkungen auf die Bereiche Software-Verifikation, Constraint-Solving in der künstlichen Intelligenz und Operations Research. Leistungsstarke Solver sind als kostenlose Open-Source-Software verfügbar . Insbesondere das konfliktgetriebene MiniSAT , das beim SAT-Wettbewerb 2005 relativ erfolgreich war , verfügt nur über etwa 600 Zeilen Code. Ein moderner paralleler SAT-Solver ist ManySAT. Es kann bei wichtigen Problemklassen superlineare Beschleunigungen erzielen. Ein Beispiel für Look-Ahead-Solver ist march_dl , das beim SAT-Wettbewerb 2007 einen Preis gewonnen hat .

Bestimmte Typen großer zufälliger erfüllbarer Instanzen von SAT können durch Survey Propagation (SP) gelöst werden . Insbesondere in Hardware-Design- und Verifikationsanwendungen werden die Erfüllbarkeit und andere logische Eigenschaften einer gegebenen propositionalen Formel manchmal basierend auf einer Darstellung der Formel als binäres Entscheidungsdiagramm (BDD) entschieden.

Fast alle SAT-Solver enthalten Zeitüberschreitungen, sodass sie in einer angemessenen Zeit beendet werden, auch wenn sie keine Lösung finden. Verschiedene SAT-Solver finden unterschiedliche Instanzen einfach oder schwer, und einige zeichnen sich durch den Nachweis von Unerfüllbarkeit aus, und andere beim Finden von Lösungen. All diese Verhaltensweisen können in den SAT-Lösungswettbewerben beobachtet werden.

Parallele SAT-Auflösung

Parallele SAT-Solver gibt es in drei Kategorien: Portfolio-, Divide-and-Conquer- und parallele lokale Suchalgorithmen. Bei parallelen Portfolios laufen mehrere verschiedene SAT-Solver gleichzeitig. Jeder von ihnen löst eine Kopie der SAT-Instanz, während Divide-and-Conquer-Algorithmen das Problem zwischen den Prozessoren aufteilen. Es gibt verschiedene Ansätze, lokale Suchalgorithmen zu parallelisieren.

Der Internationale SAT-Solver-Wettbewerb hat einen parallelen Weg, der die jüngsten Fortschritte bei der parallelen SAT-Lösung widerspiegelt. In den Jahren 2016, 2017 und 2018 wurden die Benchmarks auf einem Shared-Memory- System mit 24 Prozessorkernen ausgeführt , daher könnten Solver für verteilten Speicher oder Manycore-Prozessoren zu kurz gekommen sein.

Portfolios

Im Allgemeinen gibt es keinen SAT-Solver, der bei allen SAT-Problemen besser abschneidet als alle anderen Solver. Ein Algorithmus kann bei Probleminstanzen gut funktionieren, mit denen andere Probleme haben, aber bei anderen Instanzen wird er schlechter abschneiden. Darüber hinaus gibt es bei einer gegebenen SAT-Instanz keine zuverlässige Möglichkeit, vorherzusagen, welcher Algorithmus diese Instanz besonders schnell löst. Diese Einschränkungen motivieren den parallelen Portfolioansatz. Ein Portfolio ist ein Satz verschiedener Algorithmen oder verschiedener Konfigurationen desselben Algorithmus. Alle Solver in einem parallelen Portfolio laufen auf verschiedenen Prozessoren, um das gleiche Problem zu lösen. Wenn ein Löser beendet wird, meldet der Portfoliolöser das Problem gemäß diesem einen Löser als erfüllbar oder nicht erfüllbar. Alle anderen Solver werden beendet. Die Diversifizierung von Portfolios durch die Einbeziehung einer Vielzahl von Solvern, von denen jeder bei einer anderen Reihe von Problemen eine gute Leistung erbringt, erhöht die Robustheit des Solvers.

Viele Solver verwenden intern einen Zufallszahlengenerator . Die Diversifizierung ihrer Samen ist eine einfache Möglichkeit, ein Portfolio zu diversifizieren. Andere Diversifikationsstrategien beinhalten das Aktivieren, Deaktivieren oder Diversifizieren bestimmter Heuristiken im sequentiellen Solver.

Ein Nachteil paralleler Portfolios ist die Menge an Doppelarbeit. Wenn in den sequentiellen Solvern Klausellernen verwendet wird, kann die gemeinsame Nutzung gelernter Klauseln zwischen parallel laufenden Solvern Doppelarbeit reduzieren und die Leistung steigern. Doch selbst das parallele Ausführen eines Portfolios der besten Solver macht einen wettbewerbsfähigen parallelen Solver aus. Ein Beispiel für einen solchen Solver ist PPfolio. Es wurde entwickelt, um eine untere Grenze für die Leistung zu finden, die ein paralleler SAT-Solver liefern sollte. Trotz der großen Menge an Doppelarbeit aufgrund fehlender Optimierungen lief es auf einem Computer mit gemeinsam genutztem Speicher gut. HordeSat ist ein paralleler Portfoliolöser für große Cluster von Rechenknoten. Es verwendet im Kern unterschiedlich konfigurierte Instanzen desselben sequentiellen Solvers. Insbesondere für harte SAT-Instanzen kann HordeSat lineare Beschleunigungen erzeugen und damit die Laufzeit deutlich reduzieren.

In den letzten Jahren dominierten parallele Portfolio-SAT-Solver die Parallelstrecke der Internationalen SAT-Solver-Wettbewerbe . Bemerkenswerte Beispiele für solche Solver sind Plingeling und painless-mcomsps.

Teile und erobere

Im Gegensatz zu parallelen Portfolios versucht paralleles Divide-and-Conquer, den Suchraum zwischen den Verarbeitungselementen aufzuteilen. Divide-and-Conquer-Algorithmen, wie die sequentielle DPLL, wenden bereits die Technik der Aufteilung des Suchraums an, daher ist ihre Erweiterung zu einem parallelen Algorithmus einfach. Aufgrund von Techniken wie der Einheitsausbreitung können sich die Teilprobleme jedoch nach einer Teilung in der Komplexität erheblich unterscheiden. Somit verarbeitet der DPLL-Algorithmus typischerweise nicht jeden Teil des Suchraums in der gleichen Zeit, was zu einem herausfordernden Lastausgleichsproblem führt .

Baum, der die Look-Ahead-Phase und die resultierenden Würfel veranschaulicht.
Würfelphase für die Formel . Die Entscheidungsheuristik wählt aus, welche Variablen (Kreise) zugewiesen werden sollen. Nachdem die Cutoff-Heuristik entschieden hat, die weitere Verzweigung zu stoppen, werden die Teilprobleme (Rechtecke) unabhängig voneinander mit CDCL gelöst.

Aufgrund des nicht-chronologischen Backtrackings ist die Parallelisierung des konfliktgetriebenen Klausellernens schwieriger. Eine Möglichkeit, dies zu überwinden, ist das Cube-and-Conquer- Paradigma. Es schlägt vor, in zwei Phasen zu lösen. In der "Würfel"-Phase wird das Problem in viele Tausende bis Millionen von Abschnitten unterteilt. Dies geschieht durch einen Look-Ahead-Solver, der eine Reihe von Teilkonfigurationen findet, die als "Würfel" bezeichnet werden. Ein Würfel kann auch als Konjunktion einer Teilmenge von Variablen der ursprünglichen Formel angesehen werden. In Verbindung mit der Formel bildet jeder der Würfel eine neue Formel. Diese Formeln können unabhängig und gleichzeitig durch konfliktgesteuerte Solver gelöst werden. Da die Disjunktion dieser Formeln ist äquivalent zu der ursprünglichen Formel, wird das Problem sein erfüllbar wird, wenn eine der Formeln erfüllbar ist. Der Look-Ahead-Löser eignet sich für kleine, aber schwierige Probleme und wird daher verwendet, um das Problem schrittweise in mehrere Teilprobleme zu unterteilen. Diese Teilprobleme sind einfacher, aber immer noch groß, was die ideale Form für einen konfliktgetriebenen Löser ist. Darüber hinaus betrachten Look-Ahead-Solver das gesamte Problem, während konfliktgesteuerte Solver Entscheidungen auf der Grundlage von Informationen treffen, die viel lokaler sind. In der Würfelphase sind drei Heuristiken beteiligt. Die Variablen in den Würfeln werden durch die Entscheidungsheuristik ausgewählt. Die Richtungsheuristik entscheidet, welche Variablenzuweisung (wahr oder falsch) zuerst untersucht wird. In erfüllbaren Problemfällen ist es vorteilhaft, zuerst einen erfüllbaren Zweig auszuwählen. Die Cutoff-Heuristik entscheidet, wann die Erweiterung eines Würfels gestoppt und stattdessen an einen sequentiellen konfliktgesteuerten Solver weitergeleitet wird. Vorzugsweise sind die Würfel ähnlich komplex zu lösen.

Treengeling ist ein Beispiel für einen parallelen Solver, der das Cube-and-Conquer-Paradigma anwendet. Seit seiner Einführung im Jahr 2012 hat es mehrere Erfolge beim Internationalen SAT-Solver-Wettbewerb erzielt . Cube-and-Conquer wurde verwendet, um das Boolesche pythagoreische Tripelproblem zu lösen .

Lokale Suche

Eine Strategie für einen parallelen lokalen Suchalgorithmus für die SAT-Lösung besteht darin, mehrere variable Flips gleichzeitig auf verschiedenen Verarbeitungseinheiten auszuprobieren. Eine andere besteht darin, den oben erwähnten Portfolio-Ansatz anzuwenden, jedoch ist die gemeinsame Nutzung von Klauseln nicht möglich, da lokale Suchlöser keine Klauseln erzeugen. Alternativ ist es möglich, die lokal erstellten Konfigurationen zu teilen. Diese Konfigurationen können verwendet werden, um die Erstellung einer neuen Anfangskonfiguration zu leiten, wenn ein lokaler Solver beschließt, seine Suche neu zu starten.

Siehe auch

Anmerkungen

Verweise

Referenzen sind nach Erscheinungsdatum geordnet:

Externe Links

  • SAT-Spiel - versuchen Sie, ein boolesches Erfüllbarkeitsproblem selbst zu lösen

SAT-Problemformat

Ein SAT-Problem wird oft im DIMACS-CNF- Format beschrieben: eine Eingabedatei, in der jede Zeile eine einzelne Disjunktion darstellt. Zum Beispiel eine Datei mit den zwei Zeilen

1 -5 4 0
-1 5 3 4 0

die Formel "( x 1 ¬ x 5x 4 ) ∧ (¬ x 1x 5x 3x 4 )" darstellt.

Ein weiteres gängiges Format für diese Formel ist die 7-Bit- ASCII- Darstellung "(x1 | ~x5 | x4) & (~x1 | x5 | x3 | x4)".

  • BCSAT ist ein Tool, das Eingabedateien im menschenlesbaren Format in das DIMACS-CNF-Format umwandelt.

Online-SAT-Solver

  • BoolSAT – Löst Formeln im DIMACS-CNF-Format oder in einem benutzerfreundlicheren Format: "a und nicht b oder a". Läuft auf einem Server.
  • Logictools – Bietet verschiedene Solver in Javascript zum Lernen, Vergleichen und Hacken. Läuft im Browser.
  • minisat-in-your-browser – Löst Formeln im DIMACS-CNF-Format. Läuft im Browser.
  • SATRennesPALöst benutzerfreundlich geschriebene Formeln. Läuft auf einem Server.
  • somerby.net/mack/logic – Löst Formeln, die in symbolischer Logik geschrieben sind. Läuft im Browser.

Offline-SAT-Solver

  • MiniSAT – DIMACS-CNF-Format und OPB-Format für seinen begleitenden Pseudo-Boolean Constraint Solver MiniSat+
  • Lingeling – gewann 2011 eine Goldmedaille in einem SAT-Wettbewerb.
    • PicoSAT – ein früherer Löser aus der Lingeling-Gruppe.
  • Sat4j – DIMACS-CNF-Format. Java-Quellcode verfügbar.
  • Glukose – DIMACS-CNF-Format.
  • RSat – gewann eine Goldmedaille in einem SAT-Wettbewerb 2007.
  • UBCSAT . Unterstützt ungewichtete und gewichtete Klauseln, beide im DIMACS-CNF-Format. C-Quellcode, der auf GitHub gehostet wird .
  • CryptoMiniSat – gewann eine Goldmedaille in einem SAT-Wettbewerb 2011. Auf GitHub gehosteter C++-Quellcode . Versucht, viele nützliche Funktionen von MiniSat 2.0 Core, PrecoSat ver 236 und Glucose in einem Paket zu vereinen und viele neue Funktionen hinzuzufügen
  • Spear – Unterstützt Bit-Vektor-Arithmetik. Kann das DIMACS-CNF-Format oder das Spear-Format verwenden .
    • HyperSAT – Geschrieben, um mit B-Cubing-Suchraumbeschneidung zu experimentieren. 3. Platz in einem SAT-Wettbewerb 2005. Ein früherer und langsamerer Solver von den Entwicklern von Spear.
  • BASolver
  • ArgoSAT
  • Schneller SAT Solver – basierend auf genetischen Algorithmen .
  • zChaff – nicht mehr unterstützt.
  • BCSAT – menschenlesbares boolesches Schaltungsformat (konvertiert dieses Format auch in das DIMACS-CNF-Format und verknüpft automatisch mit MiniSAT oder zChaff).
  • gini – Go-Sprach-SAT-Solver mit verwandten Tools.
  • gophersat – Go-Sprach-SAT-Löser, der auch mit pseudo-booleschen und MAXSAT-Problemen umgehen kann.
  • CLP(B) – Boolean Constraint Logic Programming, zB SWI-Prolog .

SAT-Anwendungen

  • WinSAT v2.04 : Eine Windows-basierte SAT-Anwendung speziell für Forscher.

Konferenzen

Veröffentlichungen

Benchmarks

SAT-Lösung im Allgemeinen:

Evaluierung von SAT-Solvern

Weitere Informationen zu SAT:


Dieser Artikel enthält Material aus einer Kolumne im ACM SIGDA E-Newsletter von Prof. Karem Sakallah
Originaltext ist hier verfügbar