3-SAT

3-SAT

3-SAT ist eine Variante des Erfüllbarkeitsproblems der Aussagenlogik (Erfüllbarkeit engl.: satisfiability, kurz SAT).

Es beschäftigt sich mit der Frage, ob eine in konjunktiver Normalform vorliegende aussagenlogische Formel F, die höchstens 3 Literale pro Klausel enthält, erfüllbar ist. Ein Beispiel für eine solche Formel:

F = (\overline{x_1} \vee x_2 \vee x_3) \wedge (x_2 \vee \overline{x_3} \vee x_4) \wedge (x_1 \vee \overline{x_2})

Gesucht ist nun eine Belegung der Variablen x1 bis x4 mit 0 oder 1, für die F den Wert 1 (wahr) annimmt. Falls es eine solche Belegung gibt, ist F erfüllbar, sonst nicht. Wie bei allen NP-vollständigen Problemen ist es "einfach", einen Lösungskandidaten auf seine Gültigkeit zu überprüfen, hier also festzustellen, ob eine vorgegebene Belegung der Variablen die Formel erfüllt. Das Auffinden eines gültigen Lösungskandidaten ist jedoch im Allgemeinen "schwierig", da heute keine Methode bekannt ist, eine erfüllende Belegung in polynomieller Zeit zu finden.

Das 3-SAT Problem ist ein Constraint Satisfaction Problem.

Alle k-SAT Probleme für k\geq 3 sind NP-vollständig, 2-SAT ist NL-vollständig, 1-SAT liegt in der Komplexitätsklasse L.

Das allgemeine Erfüllbarkeitsproblem der Aussagenlogik (SAT) lässt sich auf 3-SAT polynomiell reduzieren, und somit ist 3-SAT nach dem Satz von Cook NP-vollständig.

3-SAT lässt sich wiederum u.a. auf das Cliquenproblem, das Rucksackproblem und auf den gerichteten Hamiltonkreis (DHC) polynomiell reduzieren, wodurch auch diese Probleme als NP-schwer nachgewiesen sind.

Inhaltsverzeichnis

Varianten

Exakt-3-SAT

Manchmal wird in der Definition von 3-SAT auch verlangt, dass die Klauseln genau drei Literale enthalten. Auch diese Variante des Problems ist NP-vollständig, selbst dann, wenn man zusätzlich auch noch verlangt, dass alle Literale in einer Klausel verschieden sind.

Max-3-SAT

Hier wird nicht verlangt, dass jede Klausel wahr wird, sondern möglichst viele davon. Bereits eine zufällige Belegung der Variablen liefert im Erwartungswert, dass 7/8 der Klauseln erfüllt sind (denn die Wahrscheinlichkeit, dass eine bestimmte Klausel nicht erfüllt ist, ist lediglich (1/2)^3 - vorausgesetzt, dass Literale nicht mehrfach in einer Klausel auftreten). Die Folge daraus ist auch, dass jedes derartige 3-SAT-Problem mit weniger als 8 Klauseln erfüllbar ist.
Max-3-SAT ist ebenfalls NP-vollständig, da die Reduktion zum normalen 3-SAT nur darin besteht zu fragen, ob die Gesamtanzahl der Klauseln erfüllt werden kann.

Not-All-Equal-3-SAT

Es handelt sich um 3-SAT, wobei aber nur eine Belegung akzeptiert wird, die in jeder Klausel mindestens ein falsches und ein wahres Literal bewirkt. Not-All-Equal-3-SAT ist ebenfalls NP-vollständig.

Literatur


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • SAT-Amikaro — Contexte général Champs d’action Mettre l espéranto plus particulièrement au service des personnes pour lesquelles cette langue présente en premier lieu un intérêt d ordre social, pédagogique, culturel et pratique Zone …   Wikipédia en Français

  • SAT Amikaro — Contexte général Champs d action Mettre l espéranto plus particulièrement au service des personnes pour lesquelles cette langue présente en premier lieu un intérêt d ordre social …   Wikipédia en Français

  • Sat-amikaro — Contexte général Champs d action Mettre l espéranto plus particulièrement au service des personnes pour lesquelles cette langue présente en premier lieu un intérêt d ordre social …   Wikipédia en Français

  • Sat l'Artificier — Sat, en studio pour le 2ème album solo. (Aubagne). Nom Karim Haddouche Naissance 16 septembre 1975 …   Wikipédia en Français

  • SAT-3/WASC (cable system) — SAT 3/WASC or South Atlantic 3/West Africa Submarine Cable is a submarine communications cable linking Portugal and Spain to South Africa, with connections to several West African countries along the route. It forms part of the SAT 3/WASC/SAFE… …   Wikipedia

  • Sat-Yr-9 — Sat Yr 9. Art by Alan Davis Publication information Publisher Marvel Comics/Marvel UK …   Wikipedia

  • Sat.1 Österreich — Senderlogo Ehemaliges Logo Allgemeine Informationen Empfang …   Deutsch Wikipedia

  • sat — SAT, sate, s.n. 1. Aşezare rurală a cărei populaţie se ocupă în cea mai mare parte cu agricultura. ♢ expr. Satul lui Cremene sau sat fără câini = loc fără stăpân, fără control, în care oricine poate face ce doreşte. 2. Locuitorii dintr un sat… …   Dicționar Român

  • Sat — ist ein Begriff im Hinduismus, siehe Sat Chit Ananda Die Abkürzung SAT steht für: Satellit, davon abgeleitet auch für: Satellitenfernsehen; Satellitenreceiver; SAT Anlage; SAT Kopfstelle. Körperschaften (Institutionen, Organisationen): SAT… …   Deutsch Wikipedia

  • Sat.1 Comedy — Senderlogo Allgemeine Informationen Empfang: Kabel …   Deutsch Wikipedia

  • SAT en Hispanio — SAT en Espagne SAT en Hispanio Contexte général Champs d action Information concernant l espéranto auprès des travailleurs …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”