3-SAT

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 , 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 bis 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 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.