Cuvillier Verlag

Publications, Dissertations, Habilitations & Brochures.
International Specialist Publishing House for Science and Economy

Cuvillier Verlag

De En Es
Complexity Results for Boolean Constraint Satisfaction Problems

Hard Copy
EUR 18.00 EUR 17.10

E-book
EUR 0.00

Download
PDF (1 MB)
Open Access CC BY 4.0

Complexity Results for Boolean Constraint Satisfaction Problems (English shop)

Michael Bauland (Author)

Preview

Table of Contents, Datei (22 KB)
Extract, Datei (290 KB)

ISBN-13 (Printausgabe) 3867271518
ISBN-13 (Hard Copy) 9783867271516
ISBN-13 (eBook) 9783736921511
Language English
Page Number 104
Edition 1
Volume 0
Publication Place Göttingen
Place of Dissertation Hannover
Publication Date 2007-02-14
General Categorization Dissertation
Departments Informatics
Description

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.