Titelaufnahme

Titel
Komplexität von CSP : ein algebraischer Zugang / von Klaus Neuwirth
VerfasserNeuwirth, Klaus
Begutachter / BegutachterinGoldstern, Martin
Erschienen2010
UmfangV, 59 S. : Ill.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2010
Anmerkung
Zsfassung in engl. Sprache
SpracheDeutsch
DokumenttypDiplomarbeit
Schlagwörter (DE)Komplexität CSP Algebra
URNurn:nbn:at:at-ubtuw:1-39741 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Komplexität von CSP [0.65 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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.