Satisfiability

Definition:
Das Problem Satisfiability (Erfüllbarkeit) ist die Frage, ob eine boolesche Formel erfüllbar ist. Man betrachtet meist Spezialfälle:
- 2-SAT ist eine boolesche Formel in Normalform mit 2 Literalen pro Klausel,
- 3-SAT ist eine boolesche Formel in Normalform mit 3 Literalen pro Klausel,
- SAT ist eine allgemeine boolesche Formel, wobei sich dieses Problem in polynomialer Zeit auf 3-SAT reduzieren lässt.
Wenn die Formel nicht erfüllbar ist, will man zumindest wissen, wie die freien Variablen zu wählen sind, damit möglichst viele Klauseln erfüllt sind. Dieses Problem heißt MAX-SAT, ein Spezialfall ist MAX-2-SAT.

Effiziente Lösung von 2-SAT:
Baue Graph:
- Knoten: Literale und negierte Literale
- gerichtete Kante von $u$ zu $v$: wenn $u$ false, dann muss $v$ true sein
Die Formel ist genau dann unerfüllbar, wenn ein Kreis existiert, Test in $O(n)$

Aber: MAX-2-SAT ist $NP$-schwer.

Approximationsalgorithmus für MAX-2-SAT: (Greedy-Variante)
Nimm eine Variable nach der anderen und setze sie auf 0 oder 1, so dass möglichst viele Klauseln erfüllt werden. Von $m$ Klauseln werden immer min. $\frac{1}{2} m$ erfüllt.

Approximationsalgorithmus für MAX-2-SAT: (Randomisierte Variante)
Für jede zufällige Belegung werden im Erwartunswert $\frac{3}{4} m$ Klauseln erfüllt (OR-Verknüpfung). Daher muss es eine Belegung mit min. $\frac{3}{4} m$ erfüllten Klauseln geben.

Korollar: Satisfiability $\in APX$