Direkt zum Inhalt

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.

Schreiben Sie uns!

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.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.