Algorithmen und Komplexitätstheorie von Constraint-Satisfaction-Problemen

• Antragsteller: Dr. Marc Thurley
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2012
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 195373576

Constraint-Satisfaction-Probleme (CSP) bilden einen allgemeinen Rahmen, der die Formulierung algorithmischer Probleme ermöglicht. Das Ziel solcher Probleme besteht in der Zuordnung von Werten zu gegebenen Variablen, so dass bestimmte Anforderungen (sog. Constraints) erfüllt werden. Viele wichtige Probleme können so auf sehr natürliche Weise formuliert werden. Unter ihnen sind z.B. das aussagenlogische Erfüllbarkeitsproblem (SAT), sowie Graphenfärbungs- und Planungsprobleme.Bedingt durch die Flexibilität der Formulierungsweise finden sich Constraint-Satisfaction-Probleme in vielen verschieden Bereichen der Informatik, wie der Datenbanktheorie und der künstlichen Intelligenz, wieder. In der Komplexitätstheorie nimmt die Erforschung effizient berechenbarer CSPs einen wichtigen Platz ein.Das vorgeschlagene Projekt widmet sich der Untersuchung von Constraint-Satisfaction-Problemen aus zwei verschiedenen Blickwinkeln. In einem ersten Teil sollen spezielle algorithmische Herangehensweisen an die Lösung von CSPs genau untersucht werden. Der zweite Teil dieses Projektes hat die komplexitätstheoretische Untersuchung großer Klassen von Constraint-Satisfaction-Problemen zum Ziel, die in den Rahmen der Zählkomplexität fallen.

• DFG-Verfahren: Forschungsstipendien
• Internationaler Bezug: Spanien
• Gastgeber: Professor Albert Atserias