Lexikon der Mathematik: SAT-Problem
auch satisfyability-Problem, das Erfüllbarkeitsproblem für die Konjunktion von Klauseln, also Disjunktionen von Literalen.
Diese Variante des Erfüllbarkeitsproblems spielt eine herausragende Rolle in der Geschichte der Komplexitätstheorie, da es sich dabei um das erste Problem handelt, für das Cook (Cook, Satz von) bewies, daß es NP-vollständig ist.
Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.