Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
  • Zielgruppen
  • Suche
 

Komplexitätsuntersuchungen von Constraint Satisfaction Problems

In vielen Bereichen der Informatik (Datenbanken, künstliche Intelligenz und weitere) spielen Constraint-basierte Anfragesprachen eine Rolle. Ein Programm in diesem Kontext besteht aus einer Angabe von Einschränkungen, die eine mögliche Lösung erfüllen muss. Eine Ausführung solch eines Programms liefert dann eine Lösung (etwa einen Datenbank-Eintrag), die alle Einschränkungen erfüllt. In diesem Forschungsschwerpunkt werden verschiedene Berechnungsprobleme (etwa das Finden einer Lösung, das Bestimmen der Anzahl aller Lösungen, das Aufzählen aller Lösungen) komplexitätstheoretisch untersucht.

 

Complexity of Constraints (Dagstuhl-Seminar)

Ausgewählte Publikationen