3-SAT - LinkFang.de





3-SAT


Dieser Artikel behandelt das Erfüllbarkeitsproblem der Aussagenlogik. Zum Fernsehsender 3sat siehe dort.

3-SAT ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik (von englisch satisfiability ‚Erfüllbarkeit‘, kurz SAT).

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

[math]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})[/math]

Gesucht ist nun eine Belegung der Variablen [math]x_1[/math] bis [math]x_4[/math] 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 [math]k\geq 3[/math] sind NP-vollständig, 2-SAT liegt in der Komplexitätsklasse NL, 1-SAT liegt in der Komplexitätsklasse L.

Das allgemeine Erfüllbarkeitsproblem der Aussagenlogik (SAT) lässt sich auf 3-SAT polynomiell reduzieren, und somit ist 3-SAT nach dem Satz von Cook NP-vollständig.

3-SAT lässt sich wiederum u. a. auf das Cliquenproblem, das Rucksackproblem und auf den gerichteten Hamiltonkreis (DHC) polynomiell reduzieren, wodurch auch diese Probleme als NP-schwer nachgewiesen sind.

Varianten

Exakt-3-SAT

Manchmal wird in der Definition von 3-SAT auch verlangt, dass die Klauseln genau drei Literale enthalten. Auch diese Variante des Problems ist NP-vollständig, selbst dann, wenn man zusätzlich auch noch verlangt, dass alle Literale in 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 sich um 3-SAT, wobei aber nur eine Belegung akzeptiert wird, die in jeder Klausel mindestens ein falsches und ein wahres Literal bewirkt. Not-All-Equal-3-SAT ist ebenfalls NP-vollständig.

Literatur


Kategorien: Mathematische Logik | Komplexitätstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/3-SAT (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.