Die Komplexität von Constraint-Satisfaction Problemen

• Applicant: Professor Dr. Martin Grohe
• Subject Area: Theoretical Computer Science
• Term: from 2004 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5432723

Constraint-Satisfaction-Probleme (CSP) bilden eine natürliche Klasse von algorithmischen Problemen, die wichtige Anwendungen in ganz verschiedenen Bereichen wie künstliche Intelligenz, Datenbanken, automatische Verifikation und statistische Physik haben. Prominentestes Beispiel eines CSP, das auch in diesem Projekt eine wichtige Rolle spielen soll, ist das aussagenlogische Erfüllbarkeitsproblem. Es ist seit langem bekannt, dass CSP im Allgemeinen NP-vollständig und damit, zumindest theoretisch, nicht effizient lösbar sind. In der Praxis hat es in den letzten Jahren jedoch enorme Fortschritte bei der Lösung insbesondere des aussagenlogischen Erfüllbarkeitsproblems gegeben. Inzwischen werden in industriellen Anwendungen Instanzen mit mehr als 10.000 Variablen routinemäßig gelöst. Es liegt hier also eine deutliche Diskrepanz zwischen den theoretischen "worst-case" Vorhersagen und der Praxis vor. Als Grund für diese Diskrepanz wird oft genannt, dass in der Praxis auftretende Instanzen "strukturiert" sind. Allerdings ist es völlig unklar, welche strukturellen Eigenschaften hier relevant sind und wie diese von den üblicherweise eingesetzten Algorithmen ausgenützt werden. Diese Fragen sollen im Mittelpunkt des Projekts stehen. Neben CSP und SAT als zentralem Beispiel soll hier auch eine Reihe verwandter Probleme, etwa Zählprobleme, untersucht werden.

• DFG Programme: Research Grants