Glatte Approximationen und Bedingungserfüllung

• Antragsteller: Dr. Antoine Mottet
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 534904934

Ein Constraint-Satisfaction-Problem ist ein Berechnungsproblem, bei dem eine Menge von Bedingungen und Variablen über einem Bereich gegeben ist. Die Aufgabe besteht darin zu entscheiden, ob es Werte für die Variablen gibt, die alle Bedingungen erfüllen. Solche Probleme sind in der theoretischen und angewandten Informatik von zentraler Bedeutung, und die systematische Untersuchung ihrer Komplexität mithilfe algebraischer Werkzeuge ist seit drei Jahrzehnten ein sehr aktives Forschungsfeld. Das Projekt zielt darauf ab, Constraint-Satisfaction-Probleme im Fall eines unendlichen Wertebereichs der Variablen zu untersuchen, der jedoch bestimmte Endlichkeitsbedingungen erfüllt. Bodirsky und Pinsker haben für diese Klasse von Problemen eine Komplexitätsdichotomie-Vermutung aufgestellt: Jedes dieser Probleme sollte entweder in polynomieller Zeit lösbar oder NP-vollständig sein. In diesem Bereich existiert eine Reihe algorithmischer und algebraischer Fragen, und kürzlich wurde eine neue Theorie namens "Theorie der glatten Approximationen" vorgestellt, um diese Fragen zu beantworten. Die Ziele des Projekts sind zweierlei: - Die bestehende Theorie verwenden, um Probleme zu lösen, die an der Grenze dessen liegen, was derzeit bekannt ist und die durch Anwendungen in künstlicher Intelligenz und Wissensbegründung motiviert sind. - Die Theorie weiterentwickeln, um Fortschritte bei einem Beweis der sogenannten Vermutung zur Traktierbarkeit im unendlichen Wertebereich von Bodirsky und Pinsker zu erzielen.

• DFG-Verfahren: Sachbeihilfen