3-SAT
aus Wikipedia, der freien Enzyklopädie
3-SAT ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik (Erfüllbarkeit engl.: satisfiability, kurz SAT).
Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform vorliegende aussagenlogische Formel F, die höchstens 3 Literale pro Klausel enthält, erfüllbar ist. Ein Beispiel für eine solche Formel:
Gesucht ist nun eine Belegung der Variablen x1 bis x4 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". Anders formuliert: Eine Ja-Antwort auf das gestellte Entscheidungsproblem ist durch die Angabe einer Lösung "einfach" zu belegen, eine Nein-Antwort ist dagegen nur "schwierig" zu beweisen.
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) polynomial reduzieren, wodurch auch diese Probleme als NP-schwer nachgewiesen sind.
[Bearbeiten] 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.
