Boolesche Zufriedenheitsproblem

Im Logik und Informatik, das Boolesche Zufriedenheitsproblem (manchmal genannt Aussagenerfragenproblem und abgekürzt Erfüllbarkeit, Sa oder B-sa) ist das Problem der Bestimmung, ob es eine gibt Deutung das zufrieden ein gegebenes Boolesche Formel. Mit anderen Worten, es wird gefragt, ob die Variablen einer bestimmten booleschen Formel konsistent durch die wahren oder falschen Werte ersetzt werden können, so dass die Formel auf wahr bewertet wird. Wenn dies der Fall ist, wird die Formel aufgerufen erfüllbar. Wenn andererseits keine solche Zuordnung vorliegt, ist die von der Formel ausgedrückte Funktion FALSCH Für alle möglichen variablen Zuordnungen und die Formel ist Unzufrieden. Zum Beispiel die Formel "a UND NICHT b"ist befriedigend, weil man die Werte finden kann a= Wahr und b= Falsch, was machen (a UND NICHT b) = Wahr. Im Gegensatz, "a UND NICHT a"ist nicht zufriedenbar.

SAT ist das erste Problem, das sich nachgewiesen hatte NP-Complete; sehen Cook -Levin -Theorem. Dies bedeutet, dass alle Probleme in der Komplexitätsklasse Np, einschließlich einer breiten Palette natürlicher Entscheidung und Optimierungsprobleme, sind höchstens so schwer zu lösen wie SAT. Es ist kein Algorithmus bekannt, der jedes SAT -Problem effizient löst, und es wird allgemein angenommen, dass kein solcher Algorithmus existiert; Dieser Glaube wurde jedoch mathematisch nicht bewiesen und die Frage, ob SAT a hat Polynomzeit Algorithmus entspricht dem P gegen NP -Problem, was ein berühmtes offenes Problem in der Theorie des Computers ist.

Ab 2007 können heuristische Sat-Algorithmen jedoch Probleminstanzen lösen, an denen Zehntausende von Variablen und Formeln beteiligt sind, die aus Millionen von Symbolen bestehen.^[1] was für viele praktische SAT -Probleme ausreicht, z. B., z. B., künstliche Intelligenz, Schaltungsdesign,^[2] und automatischer Theorem -Beweis.

Definitionen

A Aussagelogik Formel, auch genannt Boolescher Ausdruck, ist gebaut von Variablen, Operatoren und (Verbindung, auch bezeichnet durch ∧) oder (disjunktion, ∨), nicht (Negation, ¬) und Klammern. Eine Formel soll sein erfüllbar Wenn es durch die Zuordnung geeigneter zugewiesen werden kann logische Werte (d.h. wahr, falsch) an seine Variablen. Das Boolesche Zufriedenheitsproblem (SAT) wird eine Formel gegeben, um zu prüfen, ob sie befriedigend ist. Dies Entscheidungsproblem ist in vielen Bereichen von zentraler Bedeutung Informatik, einschließlich Theoretische Informatik, Komplexitätstheorie,^[3][4] Algorithmik, Kryptographie^[5][6] und künstliche Intelligenz.^[7]

Konjunktive normale Form

A wörtlich ist entweder eine Variable (in diesem Fall wird sie als a genannt positiver wörtlicher) oder die Negation einer Variablen (genannt a Negativ wörtlich). EIN Klausel ist eine Disjunktion von Literalen (oder einem einzigen wörtlichen). Eine Klausel wird a genannt Hornklausel Wenn es höchstens ein positives buchstäblich ist. Eine Formel ist in Konjunktive normale Form (CNF) Wenn es sich um eine Konjunktion von Klauseln (oder eine einzelne Klausel) handelt. Zum Beispiel, x₁ ist ein positives wörtliches, ¬x₂ ist ein negatives wörtliches, x₁ ∨ ¬x₂ ist eine Klausel. Die Formel (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ ¬x₁ ist in Verbindung mit normaler Form; Seine ersten und dritten Klauseln sind Hornklauseln, aber seine zweite Klausel ist nicht. Die Formel ist befriedigend, indem sie auswählen x₁= Falsch, x₂= Falsch und x₃ willkürlich, da (false ∨ ¬False) ∧ (¬False ∨ falsch ∨ x₃) ∧ ¬False bewertet (false ∨ true) ∧ (True ∨ False ∨ x₃) ∧ wahr und wiederum zu wahr ∧ wahr ∧ wahr (d. H. Zu wahr). Im Gegensatz dazu die CNF -Formel a ∧ ¬a, bestehend aus zwei Klauseln eines wörtlichen a= True oder a= Falsch Es bewertet die wahre ∧ ∧ ¬ ¬ ¬ ¬ ¬ (d. H. Falsch) oder falsches Fällen (d. H. Wieder falsch).

Für einige Versionen des SAT -Problems ist es nützlich, den Begriff von a zu definieren Verallgemeinerte konjunktive normale Form Formel, nämlich. Als Verbindung von willkürlich vielen Verallgemeinerte Klauseln, Letzteres ist der Form R(l₁, ...,l_n) für einige Boolesche Funktion R und (gewöhnliche) Literale l_i. Verschiedene Sätze erlaubter Boolesche Funktionen führen zu unterschiedlichen Problemversionen. Als Beispiel, R(¬x,a,b) ist eine verallgemeinerte Klausel, und R(¬x,a,b) ∧ R(b,y,c) ∧ R(c,d, ¬z) ist eine verallgemeinerte konjunktive normale Form. Diese Formel wird verwendet unter, mit R Der ternäre Operator zu sein, der genau dann wahr ist, wenn genau eines seiner Argumente ist.

Unter Verwendung der Gesetze von boolsche AlgebraJede Aussage -Logikformel kann in eine äquivalente konjunktive Normalform umgewandelt werden, die jedoch exponentiell länger sein kann. Zum Beispiel die Formel transformieren (x₁∧y₁) ∨ (x₂∧y₂) ∨ ... ∨ ((x_n∧y_n) In konjunktive normale Form ergibt

(x₁∨x₂∨… ∨x_n) ∧

(y₁∨x₂∨… ∨x_n) ∧

(x₁∨y₂∨… ∨x_n) ∧

(y₁∨y₂∨… ∨x_n) ∧ ... ∧

(x₁∨x₂∨… ∨y_n) ∧

(y₁∨x₂∨… ∨y_n) ∧

(x₁∨y₂∨… ∨y_n) ∧

(y₁∨y₂∨… ∨y_n);

Während Ersteres eine Disjunktion von ist n Konjunktionen von 2 Variablen, letzteres besteht aus 2ⁿ Klauseln von n Variablen.

Aber mit Verwendung der Tseytin -TransformationWir können eine äquisateleiche konjunktive Normalformformel mit Länge linear in der Größe der ursprünglichen Propositionslogikformel finden.

Komplexität

SAT war der erste bekannte NP-Complete Problem, wie nachgewiesene Stephen Cook Bei der Universität von Toronto 1971^[8] und unabhängig von Leonid Levin Bei der Nationale Akademie der Wissenschaften 1973.^[9] Bis zu diesem Zeitpunkt bestand das Konzept eines NP-Complete-Problems nicht einmal. Der Beweis zeigt, wie jedes Entscheidungsproblem in der Komplexitätsklasse Np kann sein reduziert zum SAT -Problem für CNF^{[Anmerkung 1]} Formeln, manchmal genannt Cnfsat. Eine nützliche Eigenschaft von Cooks Reduktion ist, dass sie die Anzahl der Annahme von Antworten bewahrt. Zum Beispiel entscheiden, ob eine gegebene Graph hat ein 3-farbig ist ein weiteres Problem in NP; Wenn ein Diagramm 17 gültige 3-Farben enthält, hat die SAT-Formel, die durch die Reduzierung von Cook-Levin erzeugt wird, 17 zufriedenstellende Aufgaben.

NP-Completness bezieht sich nur auf die Laufzeit der schlimmsten Fallinstanzen. Viele der Fälle, die in praktischen Anwendungen auftreten, können viel schneller gelöst werden. Sehen Algorithmen zum Lösen von SAT unter.

3-Satsfabilität

Die 3-SAT-Instanz (x ∨ x ∨ y) ∧ (¬x ∨ ¬y ∨ ¬y) ∧ (¬x ∨ y ∨ y) reduziert auf a Clique Problem. Die grünen Scheitelpunkte bilden eine 3-Clique und entsprechen der zufriedenstellenden Zuordnung x= Falsch, y= Wahr.

Wie das Erfüllbarkeitsproblem für willkürliche Formeln ist die Bestimmung der Erfüllbarkeit einer Formel in konjunktiver normaler Form, bei der jede Klausel auf höchstens drei Literale beschränkt ist. Dieses Problem wird genannt 3-sa, 3cnfsat, oder 3-Satsfabilität. Um das uneingeschränkte SAT-Problem auf 3-SAT zu reduzieren, transformieren Sie jede Klausel l₁ ∨ ⋯ ∨ l_n zu einer Verbindung von n - 2 Klauseln

(l₁ ∨ l₂ ∨ x₂) ∧

(¬x₂ ∨ l₃ ∨ x₃) ∧

(¬x₃ ∨ l₄ ∨ x₄) ∧ ⋯ ∧ ∧

(¬x_{n - 3} ∨ l_{n - 2} ∨ x_{n - 2}) ∧

(¬x_{n - 2} ∨ l_{n - 1} ∨ l_n)

wo x₂, ⋯, ⋯,x_{n - 2} sind frische Variablen, die nicht anderswo auftreten. Obwohl die beiden Formeln nicht sind logisch äquivalent, sie sind äquiszucht. Die Formel, die sich aus der Transformation aller Klauseln ergibt, ist höchstens dreimal so lang wie ihr ursprüngliches, d. H. Das Längenwachstum ist Polynom.^[10]

3-sa ist einer von Karps 21 NP-Complete-Problemeund es wird als Ausgangspunkt für den Beweis verwendet, dass auch andere Probleme sind Np-harte.^{[Anmerkung 2]} Dies geschieht durch Polynomzeitreduktion von 3-sat bis zum anderen Problem. Ein Beispiel für ein Problem, bei dem diese Methode verwendet wurde, ist die Clique Problem: Bei einer CNF -Formel, bestehend aus c Klauseln, die entsprechend Graph besteht aus einem Scheitelpunkt für jedes wörtliche und einer Kante zwischen den beiden zwei nicht kontrollierenden^{[Notiz 3]} Literale aus verschiedenen Klauseln, vgl. Bild. Die Grafik hat a c-Clique, wenn und nur wenn die Formel befriedigend ist.^[11]

Es gibt einen einfachen randomisierten Algorithmus aufgrund von Schöning (1999), der zeitlich ausgeführt wird (4/3)ⁿ wo n ist die Anzahl der Variablen im 3-SAT-Vorschlag und gelingt mit hoher Wahrscheinlichkeit, 3-SAT korrekt zu entscheiden.^[12]

Das Exponentialzeithypothese behauptet, dass kein Algorithmus 3-SAT (oder in der Tat k-Sat für jeden ${\ displayStyle k> 2}$) in exp (o(n)) Zeit (d. H. grundsätzlich schneller als exponentiell in n).

Selman, Mitchell und Levesque (1996) geben je nach Größenparametern empirische Daten zur Schwierigkeit von zufällig erzeugten 3-SAT-Formeln an. Schwierigkeit wird in zahlreichen rekursiven Aufrufen von a gemessen DPLL -Algorithmus.^[13]

3-Satentability kann verallgemeinert werden auf k-satisfability (K-sa, Auch K-CNF-sa) Wenn Formeln in CNF mit jeder Klausel berücksichtigt werden, die bis zu bis hin zu k Literale. Aber denn für jeden k ≥ 3, dieses Problem kann weder einfacher als 3-sat noch härter als SAT sein, und die beiden letzteren sind NP-Vervollständigung und müssen also K-sat sein.

Einige Autoren beschränken K-SAT auf CNF-Formeln mit Genau k Literale. Dies führt auch nicht zu einer anderen Komplexitätsklasse, wie jede Klausel l₁ ∨ ⋯ ∨ l_j mit j < k Literale können mit festen Dummy -Variablen gepolstert werdenl₁ ∨ ⋯ ∨ l_j ∨ d_j+1 ∨ ⋯ ∨ d_k. Nachdem alle Klauseln gepolstert haben, 2^k-1 zusätzliche Klauseln^{[Anmerkung 4]} müssen angehängt werden, um dies nur sicherzustellen d₁ = ⋯ = d_k= Falsch kann zu einer zufriedenstellenden Aufgabe führen. Seit k Hängt nicht von der Formellänge ab, die zusätzlichen Klauseln führen zu einer ständigen Länge. Aus dem gleichen Grund spielt es keine Rolle, ob doppelte Literale sind in Klauseln wie in erlaubt ¬x ∨ ¬y ∨ ¬y.

Sonderfälle von SAT

Konjunktive normale Form

Konjunktive normale Form (insbesondere mit 3 Literalen pro Klausel) wird häufig als kanonische Darstellung für SAT -Formeln angesehen. Wie oben gezeigt, reduziert sich das allgemeine SAT-Problem auf 3-SAT, wobei das Problem der Bestimmung der Erfüllbarkeit für Formeln in dieser Form.

Disjunktive normale Form

SAT ist trivial, wenn die Formeln auf die in beschränkt sind disjunktive normale FormDas heißt, sie sind eine Disjunktion der Konjunktionen von Literalen. Eine solche Formel ist in der Tat befriedigend, wenn und nur dann, wenn mindestens eine ihrer Konjunktionen erfüllt ist, und eine Konjunktion ist nur dann befriedigend, wenn sie nicht beides enthält x und nicht x für eine Variable x. Dies kann in der linearen Zeit überprüft werden. Darüber hinaus, wenn sie darauf beschränkt sind, in zu sein Vollständige disjunktive normale Form, in dem jede Variable in jeder Konjunktion genau einmal erscheint, können sie in konstanter Zeit überprüft werden (jede Konjunktion repräsentiert eine zufriedenstellende Zuordnung). Es kann jedoch exponentielle Zeit und Raum dauern, um ein allgemeines SAT -Problem in disjunktive normale Form umzuwandeln. zum Beispiel austauschen "∧" und "∨" in der Oben Exponentielles Blow-up-Beispiel für konjunktive normale Formen.

Genau-1 3-Satsfabilität

Links: Schäfer Reduktion einer 3-SAT-Klausel x ∨ y ∨ z. Das Ergebnis von R ist Wahr (1) Wenn genau eines seiner Argumente wahr ist, und Falsch (0) Andernfalls. Alle 8 Wertekombinationen für x,y,z werden untersucht, eine pro Zeile. Die frischen Variablen a, ...,f kann ausgewählt werden, um alle Klauseln zu befriedigen (genau eins grün Argument für jeden R) in allen Zeilen außer der ersten, wo x ∨ y ∨ z ist falsch. Recht: Eine einfachere Reduzierung mit den gleichen Eigenschaften.

Eine Variante des 3-satempfindlichen Problems ist die Ein-in-drei-3-Sa (auch unterschiedlich bekannt als 1-in-3-sa und Genau 1 3-sa). Bei einer konjunktiven normalen Form mit drei Literalen pro Klausel besteht das Problem darin, festzustellen, ob eine Wahrheitsaufgabe zu den Variablen vorhanden ist exakt ein wahres wörtliches (und damit genau zwei falsche Literale). Im Gegensatz dazu verlangt gewöhnlicher 3-SAT, dass jede Klausel hat wenigstens Ein wahres wörtliches. Formal wird ein 1-zu-drei-3-SAT-Problem als generalisierte Konjunktiv normale Form mit allen verallgemeinerten Klauseln unter Verwendung eines ternären Operators angegeben R Das ist wahr, wenn genau eines seiner Argumente ist. Wenn alle Literale einer 1-zu-drei-3-SAT-Formel positiv sind, wird das Zufriedenheitsproblem aufgerufen Ein-zu-drei-positiver 3-sa.

Ein-zu-drei-3-SAT zusammen mit seinem positiven Fall ist in der Standardreferenz als NP-Complete-Problem "LO4" aufgeführt. Computer und Unverdaulichkeit: Ein Leitfaden zur Theorie der NP-Vervollständigung durch Michael R. Garey und David S. Johnson. Es wurde erwiesen, dass 1-Drei 3-SAT von NP-Complete von durchläuft Thomas Jerome Schaefer als Sonderfall von Schäfers Dichotomie -Theorem, was behauptet, dass jedes Problem der Verallgemeinerung der Booleschen Befriedigung auf eine bestimmte Weise entweder in der Klasse P oder in der NP-Vervollständigung liegt.^[14]

Schaefer gibt eine Konstruktion, die eine einfache Verringerung der Polynomzeit von 3-sa-SAT bis zu drei Sat ermöglicht. Lassen "(x oder y oder z) "Seien Sie eine Klausel in einer 3CNF -Formel. Fügen Sie sechs frische boolesche Variablen hinzu a, b, c, d, e, und f, um diese Klausel zu simulieren und keine andere. Dann die Formel R(x,a,d) ∧ R(y,b,d) ∧ R(a,b,e) ∧ R(c,d,f) ∧ R(z,c, Falsch) ist erfüllen, indem die frischen Variablen nur dann eingestellt werden, wenn mindestens einer von x, y, oder z ist wahr, siehe Bild (links). Also jede 3-sat-Instanz mit m Klauseln und n Variablen können in eine konvertiert werden äquiszucht Ein-zu-drei-3-SAT-Instanz mit 5m Klauseln und n+6m Variablen.^[15] Eine weitere Reduzierung beinhaltet nur vier frische Variablen und drei Klauseln: R(¬x,a,b) ∧ R(b,y,c) ∧ r (c,d, ¬z) siehe Bild (rechts).

Nicht alle gleiche 3-Sat-Un infizierende

Eine andere Variante ist die Nicht alle gleiche 3-Sat-Un infizierende Problem (auch genannt Nae3sat). Bei einer konjunktiven normalen Form mit drei Literalen pro Klausel besteht das Problem darin, festzustellen, ob eine Zuordnung zu den Variablen so vorhanden ist, dass in keiner Klausel alle drei Literale den gleichen Wahrheitswert haben. Dieses Problem ist auch NP-Complete, auch wenn keine Negationssymbole durch Schäfers Dichotomie-Theorem zugelassen werden.^[14]

Linearer Sat

Eine 3-SAT-Formel ist Linearer Sat (Lsat) Wenn sich jede Klausel (als eine Reihe von Literalen angesehen) höchstens eine andere Klausel überschneidet, und außerdem, wenn sich zwei Klauseln schneiden, dann haben sie genau ein wörtliches gemeinsames. Eine LSAT-Formel kann als eine Reihe von disjunkten semi-entschlossenen Intervallen in einer Linie dargestellt werden. Die Entscheidung, ob eine LSAT-Formel befriedigend ist, ist eine NP-Vervollständigung.^[16]

2-Satsfabilität

SAT ist einfacher, wenn die Anzahl der Literale in einer Klausel auf höchstens 2 beschränkt ist. In diesem Fall wird das Problem aufgerufen 2-sa. Dieses Problem kann in Polynomzeit gelöst werden und tatsächlich ist es Komplett Für die Komplexitätsklasse Nl. Wenn zusätzlich alle oder Operationen in Literalen in geändert werden Xor Operationen werden das Ergebnis genannt Exklusiv-oder 2-Satsfabilität, was ein Problem für die Komplexitätsklasse ist Sl = L.

Hornsanschlag

Das Problem der Entscheidung der Erfüllbarkeit einer bestimmten Konjunktion von Hornklauseln wird genannt Hornsanschlag, oder Hornsa. Es kann in Polynomzeit durch einen einzelnen Schritt der gelöst werden Einheitsausbreitung Algorithmus, der das einzelne minimale Modell der Hornklauseln erzeugt (W.R.T. Der Satz von Literalen, die True zugeordnet sind). Hornsanschlag ist P-Complete. Es kann als gesehen werden P's Version des booleschen Zufriedenheitsproblems. Die Entscheidung der Wahrheit quantifizierter Hornformeln kann auch in Polynomzeit erfolgen.^[17]

Hornklauseln sind von Interesse, weil sie ausdrücken können Implikation einer Variablen aus einer Reihe anderer Variablen. In der Tat eine solche Klausel ¬x₁ ∨ ... ∨ ¬x_n ∨ y kann als umgeschrieben werden wie x₁ ∧ ... ∧ x_n → ydas heißt, wenn x₁, ...,x_n sind dann alles wahr, dann y muss auch wahr sein.

Eine Verallgemeinerung der Klasse von Hornformeln ist die von nömenswerten Hornformeln, die die Menge von Formeln ist, die durch Ersetzen einiger Variablen durch ihre jeweilige Negation in Hornform platziert werden können. Zum Beispiel, (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ ¬x₁ ist keine Hornformel, kann aber in die Hornformel umbenannt werden (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ ¬y₃) ∧ ¬x₁ durch Einführung y₃ als Negation von x₃. Im Gegensatz dazu keine Umbenennung von ((x₁ ∨ ¬x₂ ∨ ¬x₃) ∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ ¬x₁ führt zu einer Hornformel. Die Überprüfung der Existenz eines solchen Ersatzes kann in der linearen Zeit erfolgen. Daher ist die Erfüllbarkeit solcher Formeln in P, da sie gelöst werden kann, indem zuerst dieser Austausch durchgeführt und die Erfüllbarkeit der resultierenden Hornformel geprüft wird.

Eine Formel mit 2 Klauseln kann unzufrieden (rot), 3 -zufrieden (grün), xor-3-unzufrieden (blau) oder/und 1-zu-3 Die 1. (Hor) und 2. (Vert) Klausel.

Xor-satisfability

Ein weiterer Sonderfall ist die Klasse von Problemen, bei denen jede Klausel XOR enthält (d. H. Exklusiv oder) und nicht (einfach) oder Operatoren.^{[Anmerkung 5]} Das ist in P, da eine XOR-SAT-Formel auch als System der linearen Gleichungen MOD 2 angesehen werden kann und in der Kubikzeit von gelöst werden kann Gaußsche Eliminierung;^[18] Ein Beispiel finden Sie in der Box. Diese Neuaufstellung basiert auf dem Verwandtschaft zwischen Booleschen Algebren und Booleschen Ringenund die Tatsache, dass das arithmetische Modulo zwei bildet a endliches Feld. Seit a Xor b Xor c bewertet true, wenn und nur dann genau 1 oder 3 Mitglieder von {a,b,c} sind wahr, jede Lösung des 1-in-3-SAT-Problems für eine gegebene CNF -Sat, vgl. Bild. Infolgedessen ist es für jede CNF-Formel möglich, das von der Formel definierte XOR-3-SAT-Problem zu lösen, und basierend auf dem Ergebnis schließen entweder, dass das 3-SAT-Problem lösbar ist oder dass das 1-in-3- SAT -Problem ist unlösbar.

Vorausgesetzt dass das Komplexitätsklassen P und NP sind nicht gleichweder 2- noch Horn- noch XOR-Satisfability sind im Gegensatz zu SAT NP-Vervollständigung.

Schäfers Dichotomie -Theorem

Die obigen Einschränkungen (CNF, 2CNF, 3CNF, Horn, XOR-sa) banden die betrachteten Formeln so zu Konjunktionen von Subformeln; Jede Restriktion gibt eine bestimmte Form für alle Subformeln an: Beispielsweise können nur binäre Klauseln in 2CNF Subformeln sein.

Schaefers Dichotomie-Theorem stellt fest, dass das entsprechende Erfüllbarkeitsproblem für jede Beschränkung der Booleschen Funktionen verwendet werden kann, die zur Bildung dieser Subformeln verwendet werden können. Die Mitgliedschaft in P über die Erfüllbarkeit von 2CNF-, Horn- und XOR-SAT-Formeln ist Sonderfälle dieses Satzes.^[14]

Die folgende Tabelle fasst einige häufige Varianten des SAT zusammen.

Erweiterungen des SAT

Eine Erweiterung, die seit 2003 erhebliche Popularität erlangt hat Befriedigungsmodulo -Theorien (SMT) Das kann CNF-Formeln mit linearen Einschränkungen, Arrays, All-Differenz-Einschränkungen, Anrichen, anreichern können. uninterpretierte Funktionen,^[19] usw. Solche Erweiterungen bleiben typischerweise NP-Complete, aber jetzt sind sehr effiziente Löser verfügbar, die viele solcher Arten von Einschränkungen verarbeiten können.

Das Problem der Erfüllbarkeit wird schwieriger, wenn beides "für alle" (∀) und "da existiert" (∃) Quantifizierer dürfen die booleschen Variablen binden. Ein Beispiel für einen solchen Ausdruck wäre ∀x ∀y ∃z (x ∨ y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z); es ist gültig, da für alle Werte von x und yein angemessener Wert von z kann gefunden werden, nämlich. z= Wahr, wenn beide x und y sind falsch und z= Falsch sonst. SAT selbst (stillschweigend) verwendet nur ∃ Quantifizierer. Wenn stattdessen nur ∀ Quantifizierer zulässig sind, sind die sogenannten Tautologie Problem wird erhalten, was ist CO-NP-Complete. Wenn beide Quantifizierer erlaubt sind, wird das Problem als das genannt Quantifiziertes Problem der Booleschen Formel (QBF), was gezeigt werden kann PSPACE-Complete. Es wird allgemein angenommen, dass PSPACE-Vervollständigungsprobleme in NP streng schwieriger sind als jedes Problem, obwohl dies noch nicht bewiesen wurde. Verwenden von hoch parallele P -Systeme, QBF-SAT-Probleme können in der linearen Zeit gelöst werden.^[20]

Gewöhnliche SAT fragt, ob es mindestens eine variable Zuordnung gibt, die die Formel wahr macht. Eine Vielzahl von Varianten befasst sich mit der Anzahl solcher Aufgaben:

• Maj-sa fragt, ob die Mehrheit aller Aufgaben die Formel wahr macht. Es ist bekannt, dass es vollständig ist für Pp, eine probabilistische Klasse.
• #SatDas Problem des Zählens, wie viele variable Zuordnungen eine Formel erfüllen, ist ein Zählproblem, kein Entscheidungsproblem und ist ist #P-Complete.
• Einzigartiger Sat^[21] Ist das Problem der Bestimmung, ob eine Formel genau eine Zuordnung hat. Es ist vollständig für uns,^[22] das Komplexitätsklasse Beschreibung von Problemen, die durch eine nicht deterministische Polynomzeit lösbar sind Turing Maschine Dies akzeptiert, wenn genau ein nicht deterministisches Akzeptanzpfad vorhanden ist und etwas anderes ablehnt.
• Eindeutig-sat ist der Name, der dem Erfüllbarkeitsproblem gegeben wird, wenn die Eingabe ist eingeschränkt zu Formeln mit höchstens eine zufriedenstellende Aufgabe. Das Problem wird auch genannt USAat.^[23] Ein Lösungsalgorithmus für eindeutiges SAT darf ein Verhalten, einschließlich endloser Schleifen, auf einer Formel mit mehreren zufriedenstellenden Aufgaben aufweisen. Obwohl dieses Problem einfacher erscheint, haben Valiant und Vazirani gezeigt^[24] das, wenn es ein praktisches (d.h. Randomisierte Polynomzeit) Algorithmus, um es zu lösen, dann alle Probleme in Np kann genauso leicht gelöst werden.
• Max-sa, das Maximaler Erfüllbarkeitsproblem, ist ein Fnp Verallgemeinerung von SAT. Es fragt nach der maximalen Anzahl von Klauseln, die durch jede Zuordnung erfüllt werden können. Es hat effizient Näherungsalgorithmen, aber np-hard, um genau zu lösen. Schlimmer noch, es ist es APX-Complete, was bedeutet, dass es keine gibt Polynom-Zeit-Approximationsschema (PTAs) für dieses Problem, es sei denn, p = np.
• Wmsat ist das Problem, eine Zuordnung von Mindestgewicht zu finden, die eine monoton Boolesche Formel erfüllt (d. H. Eine Formel ohne Negation). Die Gewichte von Propositionsvariablen sind im Eingang des Problems angegeben. Das Gewicht einer Zuordnung ist die Summe der Gewichte echten Variablen. Dieses Problem ist NP-Complete (siehe th. 1 von ^[25]).

Andere Verallgemeinerungen beinhalten die Erfüllbarkeit für Erste- und Logik zweiter Ordnung, Probleme mit der Einschränkung der Zufriedenheit, 0-1 Ganzzahlprogrammierung.

Eine befriedigende Aufgabe finden

Während SAT ist a Entscheidungsproblem, das Suchproblem Die Suche nach einer befriedigenden Aufgabe reduziert sich auf SAT. Das heißt, jeder Algorithmus, der korrekt antwortet, wenn eine Instanz von SAT lösbar ist, kann verwendet werden, um eine zufriedenstellende Zuordnung zu finden. Zunächst wird die Frage auf der angegebenen Formel φ gestellt. Wenn die Antwort "Nein" ist, ist die Formel nicht zufriedenstellbar. Andernfalls wird die Frage auf der teilweise instanziierten Formel φ gestellt{x₁= True}, d.h. φ mit der ersten Variablen x₁ durch True ersetzt und entsprechend vereinfacht. Wenn die Antwort "Ja" ist, dann x₁= Wahr, sonst x₁= Falsch. Die Werte anderer Variablen können anschließend auf die gleiche Weise gefunden werden. In Summe, n+1 Läufe des Algorithmus sind erforderlich, wo n ist die Anzahl der unterschiedlichen Variablen in φ.

Diese Eigenschaft wird in mehreren Theoreme in der Komplexitätstheorie verwendet:

Np ⊆ P/poly ⇒ PH = Σ₂ (Karp -Lipton -Theorem)

Np ⊆ BPP ⇒ Np = RP

P = Np ⇒ FP = Fnp

Algorithmen zum Lösen von SAT

Da das SAT-Problem NP-Vervollständigung ist, sind dafür nur Algorithmen mit exponentieller schlimmster Fall bekannt. Trotzdem wurden in den 2000er Jahren effiziente und skalierbare Algorithmen für SAT entwickelt und haben zu dramatischen Fortschritten bei unserer Fähigkeit beigetragen, Probleminstanzen mit zehn Tausenden von Variablen und Millionen von Einschränkungen (d. H. Klausel) automatisch zu lösen.^[1] Beispiele für solche Probleme in elektronische Designautomatisierung (EDA) einschließen Formale Äquivalenzprüfung, Modellprüfung, formelle Überprüfung von Pipeline -Mikroprozessoren,^[19] Automatische Testmustererzeugung, Routing von Fpgas,^[26] Planung, und Planungsprobleme, usw. Ein satlösender Motor wird auch als wesentlicher Bestandteil der elektronische Designautomatisierung Werkzeugkasten.

Zu den wichtigsten Techniken, die von modernen SAT -Löser verwendet werden Davis -Putnam -logemann -Loveland -Algorithmus (oder dpll), Konfliktorientiertes Lernen (CDCL) und stochastisch lokale Suche Algorithmen wie Walksat. Fast alle SAT-Löser enthalten Auszeiten, sodass sie in angemessener Zeit enden, auch wenn sie keine Lösung finden können. Unterschiedliche SAT -Löser finden unterschiedliche Instanzen einfach oder hart, und einige zeichnen sich bei der Suche nach Lösungen und anderen als Unzufriedenheit.

SAT-Löser werden in SAT-Lösungs-Wettbewerben entwickelt und verglichen.^[27] Moderne SAT -Solvers haben unter anderem auch erhebliche Auswirkungen auf die Bereiche der Softwareverifizierung, Einschränkung der künstlichen Intelligenz und Operationsforschung.

Siehe auch

• Unzufriedener Kern
• Befriedigungsmodulo -Theorien
• Sa zählen
• Planar saß
• Karloff -Zwick -Algorithmus
• Erfüllbarkeit der Schaltung

Anmerkungen

Externe Links

• SAT -Spiel: Versuchen Sie selbst, ein Boolesche Befriedigungsproblem zu lösen
• Die International SAT -Wettbewerbswebsite
• Internationale Konferenz über Theorie und Anwendungen von Erfüllbarkeitstests
• Journal über Zufriedenheit, Boolesche Modellierung und Berechnung
• SAT LIVE, eine aggregierte Website für die Erforschung des Befriedigungsproblems
• Jährliche Bewertung von Maxsat Solvers

Verweise

Zusätzliche Referenzen bis zum Datum der Veröffentlichung:

Dieser Artikel enthält Material aus einer Spalte im ACM Sigda E-Newsletter durch Prof. Karem Sakallah
Der Originaltext ist verfügbar hier