Bibliographic Metadata

Title
Komplexität von CSP : ein algebraischer Zugang / von Klaus Neuwirth
AuthorNeuwirth, Klaus
CensorGoldstern, Martin
Published2010
DescriptionV, 59 S. : Ill.
Institutional NoteWien, Techn. Univ., Dipl.-Arb., 2010
Annotation
Zsfassung in engl. Sprache
LanguageGerman
Document typeThesis (Diplom)
Keywords (DE)Komplexität CSP Algebra
URNurn:nbn:at:at-ubtuw:1-39741 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Komplexität von CSP [0.65 mb]
Links
Reference
Classification
Abstract (German)

Diese Arbeit beschäftigt sich mit einer Klasse von Problemen, den sogenannten \em Constraint Satisfaction Problem\em s, kurz CSP, die zahlreiche "`natürliche"' (das heißt nicht zum Zweck der Komplexitätsbestimmung konstruierte) Probleme umfasst. Anfangs wurde vermutet, dass CSP Probleme enthält, die P und NP trennen. Deren Existenz wiederum wäre ein Beweis für P$ eq$NP, das wohl populärste ungelöste Problem der Mathematik beziehungsweise Informatik.

Im Lauf der Erforschung von CSP, die ursprünglich von der Theoretischen Informatik ausging, erwiesen sich Hilfsmitteln aus der Algebra als mächtige Werkzeuge mit deren Hilfe sich elegante Resultate erzielen ließen. Durch diese Erkenntnis wurde die weitere Auseinandersetzung mit diesem Thema belebt und es konnten beachtliche Fortschritte erzielt werden, die jedoch in die Richtung weisen, dass wohl doch jedes Problem in CSP entweder in P liegt oder schon NP-vollständig ist.

Nichtsdestotrotz floriert das Forschungsgebiet nach wie vor, der praktischen Bedeutung vieler CSP Probleme geschuldet.

Im ersten Kapitel wird ein kurzer Überblick über die zugrundeliegenden Definitionen aus der Theoretischen Informatik gegeben, da das Verständnis gewisser Begrifflichkeiten für die Motivation und Interpretation der späteren Ergebnisse unerlässlich ist. In Kapitel 2 folgt eine Einführung in die notwendigen algebraischen Grundlagen sowie eine formale Definition von CSP. Im dritten Kapitel schließlich werden die bahnbrechenden Resultate von Jeavons et al. präsentiert, bevor im vierten und letzten Teil weiterführende Ergebnisse aufgeführt werden, die mit zwar fortgeschritteneren als den hier vorgestellten, jedoch auf ihnen aufbauenden Mitteln erzielt wurden. Das vierte Kapitel soll also zeigen, wie viele unterschiedliche Gebiete Einfluss auf die Komplexitätsuntersuchungen von CSP hatten und wie rasant seit der Entwicklung des algebraischen Zugangs weitere Fortschritte erzielt werden konnten.