50 Jahre Uni Lübeck

Institut für Theoretische Informatik

Deskriptive Komplexitätstheorie


Veranstaltungsart und -inhalt

Titel Deskriptive Komplexitätstheorie
Dozenten Prof. Tantau, Elberfeld
Einordnung Hauptseminar
Diplom-Studiengang ab 5. Semester
Master-Studiengang ab 1. Semester
Inhalte In der Komplexitätstheorie untersucht man, welche Probleme sich mit bestimmten ressourcenbeschränkten Maschinenmodellen lösen lassen. Zum Beispiel lässt sich die Frage, ob es einen Weg zwischen zwei Knoten in einem Graphen gibt, durch eine Turingmaschine mit logarithmischem Platzaufwand beantworten. Die Maschine entscheidet, ob der Graph eine bestimmte Eigenschaft besitzt. In der deskriptiven Komplexitätstheorie wird untersucht mit welchen logischen Sprachen sich solche Eigenschaften beschreiben lassen. Das obige Wegeproblem lässt sich zum Beispiel nicht durch eine prädikatenlogische Formel erster Stufe (First-Order Logic) beschreiben. Durch eine etwas mächtigere Logik wird eine Beschreibung des Wegeproblems aber möglich.

In dem Seminar werden anhand von Vorträgen und Ausarbeitungen die Grundlagen der deskriptiven Komplexitätstheorie besprochen, wichtige Resultate vorgestellt und Zusammenhänge zu sequentiellen und parallelen Maschinenmodellen hergestellt.
Termine Do. 16:00 – 18:00, ITCS Seminarraum 2021
Wiki Wiki zum Seminar »Deskriptive Komplexitätstheorie«