Neuwirth, K. (2010). Komplexität von CSP : ein algebraischer Zugang [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-39741
E104 - Institut für Diskrete Mathematik und Geometrie
-
Date (published):
2010
-
Number of Pages:
59
-
Keywords:
Komplexität CSP Algebra
de
Abstract:
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.<br />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.<br />Nichtsdestotrotz floriert das Forschungsgebiet nach wie vor, der praktischen Bedeutung vieler CSP Probleme geschuldet.<br />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.
de
Additional information:
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers Zsfassung in engl. Sprache