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

• Applicant: Professor Dr. Heribert Vollmer
• Subject Area: Theoretical Computer Science
• Term: from 2003 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants