3-SAT

Stichpunkte

Allgemein
	Der Name eines öffentlich-rechtlichen Fernsehsenders ist 3sat. 3-SAT ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik (Erfüllbarkeit engl.: satisfiability
	kurz SAT)
	Es beschäftigt sich mit der Frage
	erfüllbar ist
	ob eine in konjunktiver Normalform vorliegende aussagenlogische Formel <math>F<math>
	die höchstens 3 Literale pro Klausel enthält
	für die F den Wert 1 (wahr) annimmt
	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
	ist F erfüllbar
	Falls es eine solche Belegung gibt
	sonst nicht
	ob sie F wahr macht
	aber "schwierig"
	eine passende Belegung zu finden
	für eine gegebene Belegung der Variablen zu testen
	Wie bei allen NP-vollständigen Problemen ist es einfach bzw. in kurzer Zeit möglich
	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-hart nachgewiesen sind
	selbst dann
	dass alle Literale in einer Klausel verschieden sind.
	wenn man zusätzlich auch noch verlangt
	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

Dieser Artikel basiert auf dem Artikel 3-SAT aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.