Navigation

Springe zum Hauptinhalt
Fakultät für Informatik
Informatik-Kolloquien

136. Informatik-Kolloquium

Vortrag

Herr Dr. H. Schnoor

Christian-Albrechts-Universität zu Kiel
Arbeitsgruppe Theoretische Informatik
Institut für Informatik

"Komplexität von Erfüllbarkeitsproblemen "




Donnerstag, 15.05.2008
14:00 Uhr, 1/336

Alle interessierten Personen sind herzlich eingeladen!


Abstract:

Erfüllbarkeitsprobleme spielen eine zentrale Rolle in der Komplexitätstheorie und stellen kanonische vollständige Probleme für viele Standard-Komplexitätsklassen. Eine Möglichkeit, viele verschiedene Erfüllbarkeitsprobleme in einem gemeinsamen formalen Rahmen zu betrachten, liefern Constraint Satisfaction Probleme. In dem Vortrag geht es um die Untersuchung der Komplexität von Constraint Satisfaction Problemen, und um die mathematischen Hilfsmittel, die man hierfür benutzt.

Presseartikel