3-SAT

Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Der Name eines öffentlich-rechtlichen Fernsehsenders ist 3sat .

3-SAT ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik ( SAT ).

Es beschäftigt sich mit der Frage eine in konjunktiver Normalform vorliegende aussagenlogische Formel F die höchstens 3 Literale pro Klausel enthält erfüllbar ist.

3-SAT lässt sich polynomial reduzieren auf das Erfüllbarkeitsproblem der Aussagenlogik und ist somit NP-vollständig .

Auf 3-SAT wiederum lassen sich das Cliquenproblem das Rucksackproblem und der gerichtete Hamiltonkreis polynomial reduzieren.

Bücher zum Thema 3-SAT

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

Impressum • Lesezeichen setzen • Seite versenden • Seite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/3-SAT_(Begriffserkl%E4rung).html">3-SAT </a>