Complexity Results for Boolean Constraint Satisfaction Problems

Vorschau

Inhaltsverzeichnis, Datei (22 KB)
Leseprobe, Datei (290 KB)

Meine Dissertation befasst sich mit Boole’schen Constraint Satisfaction Problemen (kurz: CSP). Ein Constraint besteht aus einer Menge von Variablen und einer (Boole’schen) Relation, die die Belegungen bestimmter Tupel von Variablen einschränkt. Ein CSP ist
dann die Frage, ob es zu einer gegebenen Menge von Constraints eine Belegung aller Variablen gibt, die alle Constraints gleichzeitig erfüllt. Dieses CSP und einige seiner Derivationen werden unter komplexitätstheoretischen Aspekten betrachtet. Als wichtiges Instrument zur Bestimmung der Komplexität von CSP wird die algebraische Methode verwendet. Diese nutzt die von Emil Post gefundene vollständige
Klassifikation aller unter Superposition abgeschlossener Klassen Boole’scher Funktionen
(Clones). Der Abschluss einer Menge von Funktionen unter Superposition bedeutet dabei, dass die Menge der Funktionen unter beliebigen Kompositionen abgeschlossen ist. Der nach ihm benannte Post’sche Graph zeigt die vollständige Inklusionsstruktur der
Clones. Hiermit konnten in Verbindung mit der Galoistheorie schon viele elegante Beweise geführt werden. Unter anderem wurde so auch das Dichotomieergebnis von Thomas Schaefer erneut bewiesen. Dieses besagt, dass das Boole’sche CSP in Abhängigkeit von den zugelassenen Boole’schen Constraints entweder in P oder NP-vollständig ist.