Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers
-
dc.description
Zsfassung in engl. Sprache
-
dc.description.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
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Komplexität CSP Algebra
de
dc.title
Komplexität von CSP : ein algebraischer Zugang
de
dc.title.alternative
Complexity of CSP - an Algebraic Approach
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Klaus Neuwirth
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
tuw.publication.orgunit
E104 - Institut für Diskrete Mathematik und Geometrie