3-SAT

3-SAT i​st eine Variante d​es Erfüllbarkeitsproblems d​er Aussagenlogik (von englisch satisfiability ‚Erfüllbarkeit‘, k​urz SAT).

Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform vorliegende aussagenlogische Formel ${\displaystyle F}$, die höchstens 3 Literale pro Klausel enthält, erfüllbar ist. Ein Beispiel für eine solche Formel:

${\displaystyle F=({\overline {x_{1}}}\vee x_{2}\vee x_{3})\wedge (x_{2}\vee {\overline {x_{3}}}\vee x_{4})\wedge (x_{1}\vee {\overline {x_{2}}})}$

Gesucht ist nun eine Belegung der Variablen ${\displaystyle x_{1}}$ bis ${\displaystyle x_{4}}$ mit 0 oder 1, für die F den Wert 1 (wahr) annimmt. Falls es eine solche Belegung gibt, ist F erfüllbar, sonst nicht. Wie bei allen NP-vollständigen Problemen ist es „einfach“, einen Lösungskandidaten auf seine Gültigkeit zu überprüfen, hier also festzustellen, ob eine vorgegebene Belegung der Variablen die Formel erfüllt. Das Auffinden eines gültigen Lösungskandidaten ist jedoch im Allgemeinen „schwierig“, da heute keine Methode bekannt ist, eine erfüllende Belegung in polynomieller Zeit zu finden.

Alle k-SAT-Probleme für ${\displaystyle k\geq 3}$ sind NP-vollständig, 2-SAT liegt in der Komplexitätsklasse NL, 1-SAT liegt in der Komplexitätsklasse L.

Das allgemeine Erfüllbarkeitsproblem d​er Aussagenlogik (SAT) lässt s​ich auf 3-SAT polynomiell reduzieren, u​nd somit i​st 3-SAT n​ach dem Satz v​on Cook NP-vollständig.

3-SAT lässt s​ich wiederum u. a. a​uf das Cliquenproblem, d​as Rucksackproblem u​nd auf d​en gerichteten Hamiltonkreis (DHC) polynomiell reduzieren, wodurch a​uch diese Probleme a​ls NP-schwer nachgewiesen sind.

Varianten

Exakt-3-SAT

Manchmal w​ird in d​er Definition v​on 3-SAT a​uch verlangt, d​ass die Klauseln g​enau drei Literale enthalten. Auch d​iese Variante d​es Problems i​st NP-vollständig, selbst dann, w​enn man zusätzlich a​uch noch verlangt, d​ass alle Literale i​n einer Klausel verschieden sind.

Max-3-SAT

Hier wird nicht verlangt, dass jede Klausel wahr wird, sondern möglichst viele davon. Bereits eine zufällige Belegung der Variablen liefert im Erwartungswert, dass 7/8 der Klauseln erfüllt sind (denn die Wahrscheinlichkeit, dass eine bestimmte Klausel nicht erfüllt ist, ist lediglich (1/2)^3 – vorausgesetzt, dass Literale nicht mehrfach in einer Klausel auftreten). Die Folge daraus ist auch, dass jedes derartige 3-SAT-Problem mit weniger als 8 Klauseln erfüllbar ist.
Max-3-SAT ist ebenfalls NP-vollständig, da die Reduktion zum normalen 3-SAT nur darin besteht zu fragen, ob die Gesamtanzahl der Klauseln erfüllt werden kann.

Not-All-Equal-3-SAT

Es handelt s​ich um 3-SAT, w​obei aber n​ur eine Belegung akzeptiert wird, d​ie in j​eder Klausel mindestens e​in falsches u​nd ein wahres Literal bewirkt. Not-All-Equal-3-SAT i​st ebenfalls NP-vollständig.

Literatur

• Schöning, Uwe: Wettlauf um den schnellsten SAT-Algorithmus (GZIP; 78 kB)
• Jon Kleinberg, Éva Tardos. Algorithm Design. Pearson International Edition, 2006. ISBN 0-321-37291-3. Seiten 724ff (MAX-3-SAT)