Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDienstag, 30. September 2014 

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.

ImpressumLesezeichen setzenSeite versendenSeite drucken

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