Editorial Cuvillier

Publicaciones, tesis doctorales, capacitaciónes para acceder a una cátedra de universidad & prospectos.
Su editorial internacional especializado en ciencias y economia

Editorial Cuvillier

De En Es
Complexity Results for Boolean Constraint Satisfaction Problems

Impresion
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 (Tienda española)

Michael Bauland (Autor)

Previo

Indice, Datei (22 KB)
Lectura de prueba, 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.

ISBN-10 (Impresion) 3867271518
ISBN-13 (Impresion) 9783867271516
ISBN-13 (E-Book) 9783736921511
Idioma Inglés
Numero de paginas 104
Edicion 1
Volumen 0
Lugar de publicacion Göttingen
Lugar de la disertacion Hannover
Fecha de publicacion 14.02.2007
Clasificacion simple Tesis doctoral
Area Informática