Constraint-Satisfaction-Probleme: algebraische Struktur und komplexitätstheoretische Klassifikationen

• Antragsteller: Professor Dr. Heribert Vollmer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2003 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5402405

Programmiersprachen aus dem Gebiet der künstlichen Intelligenz oder Anfragesprachen aus dem Gebiet der Datenbanken sind oft so aufgebaut, dass eine Reihe von Einschränkungen (Constraints) formuliert wird und die Ausführung des Programms nichts anderes ist als die Suche nach einer Lösung (etwa einem Datenbank-Eintrag), die alle Einschränkungen erfüllt. Die Frage, ob eine Lösung eines solchen sog. Constraint Satisfaction Problems existiert, ist im Allgemeinen NP-vollständig, also nach derzeitigem Wissensstand nicht mit vertretbarem Zeitaufwand durch einen Rechner lösbar. Im beantragten Projekt sollen verschiedene Typen von Anfragen aus komplexitätstheoretischer Sicht untersucht und nach ihrer Berechnungsschwierigkeit klassifiziert werden. Methodisch soll dabei auf Strukturuntersuchungen von Constraints mit Hilfsmitteln aus der universellen Algebra zurückgegriffen werden. Zunächst ist an eine Untersuchung des Spezialfalls der Booleschen Constraints, also der Constraints über einem zweielementigen Grundbereich, gedacht. Sodann sollen die dabei gewonnenen Erkenntnisse auf den Fall beliebiger endlicher Grundbereiche ausgedehnt werden.

• DFG-Verfahren: Sachbeihilfen