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
Schreiben Sie uns!