Algorithmen für das Erfüllbarkeitsproblem SAT

teilweise aus einem Vortrag vonMelanie Schmidt (Uni Dortmund)

mit Ergänzungen aus einer Präsentation von Carsten Sinz

(Uni Tübingen)

2/11

Variablen x1,x2,x3,x4,x5,x6

x3 ¬x2 x5( ) ( ¬x1 ) ( x1 ¬x2 x3 ¬x4 x6 )

Problem für 5-SAT

Klausel

n = Anzahl der Variablen = 6

Das Erfüllbarkeitsproblem K-KNF-SAT

3/11

Das Erfüllbarkeitsproblem K-KNF-SAT

Also:• Gegeben ist eine Menge von Klauseln mit jeweils bis

zu k Literalen • Eine Klausel hat die Form (u1 u2 … ul),

l k, wobei ui {x1,…,xn} {¬x1,…,¬xn}• Gesucht: Eine Belegung der Variablen

x1,… ,xn mit Wahrheitswerten {0, 1}, so dass die Auswertung der Formel 1 ergibt.

Davis Putnam Loveland Logeland-Algorithmus

• Konstruiere Belegung inkrementell• Verwende Backtracking für

Wahrheitswertezuweisung im Falle, dass eine nicht erfüllende Belegung konstruiert wird

• Verwende Propagierung von festgelegten Variablen zur “Verkleinerung” von Disjuntionen (Einer-Klauseln legen Zuweisung fest)

• Pure-Literal Elimination

2-SAT

• Beh.: Es existiert ein Algorithmus in polynomieller Zeit.Bew.: Resolution produziert max. O(n2) Klauseln

• Geht es noch besser? Aspvall et al. 1980

6/11

• (¬x3) (x2 x3) (¬x1 ¬x2) (x3 x1)

• (a b) = (¬a b)

2-SAT Algorithmus

• (¬x3 ¬x3) (x2 x3) (¬x1 ¬x2) (x3 x1 )

• (a) = (a a)• (a b) = (¬a b)

(a b) = (¬b a)

X1

¬X2¬X1

X2 X3

¬X3¬X1

X2 X3

¬X3

X3

¬X3

7/11

2-SAT Algorithmus

• Eine 2-KNF-Formel ist unerfüllbar

im Graphen GF existiert ein Zyklus der Form xi … ¬xi … xi

gdw.

8/11

Zyklus mit xi und ¬xi dann F unerfüllbar

• Annahme: Es gibt eine erfüllende Belegung a.

Dann muss für a gelten, dass xi=1 und xi =0. Das ist ein Widerspruch.

9/11

F unerfüllbardann existiert Zyklus mit xi und ¬ xi

• Beweis mit Induktion über Anzahl der Variablen n:- n=1.

- F muss die Form (x1) (¬x1) haben GF hat einen Zyklus.

- n-1n. - Wähle beliebiges x aus {x1,…,xn}.

- Bilde Fx=0 und Fx=1

GFx=0 und GFx=1 enthalten Zyklen mit y und ¬y (y aus {x1,…,xn})- Zeige, dass daraus folgt:

GF enthält einen Zyklus mit x und ¬x

X1 ¬X1

10/11

GF enthält einen Zyklus mit x und ¬x

• Trivial:Einer der Zyklen aus GFx=0 und GFx=1 ist auch in GF enthalten (x=y)

• Sonst:Zeige, dass es in GF die Verbindungen ¬x … x und x … ¬x gibtund dann existiert ein Zyklus mit x und ¬x

y

¬y¬x ¬y

x y

11/11

Pfade in GF

• Beh.: ¬x … x in GF

– Fall 1: F enthält (x), also (x x) und damit ¬x x– Fall 2: F enthält (x z)

• GF enthält ¬x z und ¬z x

• Fx=0 enthält nur (z)

• Ann.: der Zyklus in GFx=0 enthält ¬z z,dann gilt: GF enthält ¬z z nicht (denn x kommt hinzu)

daraus folgt, in GF gibt es ¬x z … ¬z x

• Beh.: x … ¬x in GF

– Analog mit (¬x) sowie Fx=1 und GFx=1

12/11

Zyklen mit x und ¬x finden

• als All-Pair-Shortest-Paths– Problem– mit unendlichen Kosten für nichtvorhandene Kanten– für alle x überprüfen:

(x,¬x) und (¬x,x) < ? – Laufzeit O(n3)

• Besser: mit Tiefensuche (Aspvall et al. 1980)– in stark zusammenhängende Komponenten zerlegen

(SCC-Algorithmus)– Topologisches Sortieren– O(m+n), m=Anzahl der Kanten in G(F)

= 2x Anzahl der Klauseln in F

2-SAT: Aspvall Algorithmus

2-SAT: Aspvall Algorithmus