Instituts-Logo Logik in der Informatik
Prof. Dr. Martin Grohe 		Humboldt-Logo

Vorlesung Logik und Komplexität
(Sommersemester 2011)

Aktuelles   Logbuch   Einführung   Material   Termine   Aufgaben   Prüfung   Literatur

Aktuelles

An dieser Stelle finden Sie im Laufe der Vorlesung aktuelle Mitteilungen.

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen und gelegentlich auch Korrekturen und sonstige Bemerkungen.

Einführung

Thema dieser Vorlesung ist der Zusammenhang zwischen logischer Beschreibbarkeit und Komplexität. Ein Schwerpunkt ist die deskriptive Komplexitätstheorie, in der der Zusammenhang zwischen Beschreibungskomplexität und klassischer Berechnungskomplexität von Problemen untersucht wird. So können wichtige Komplexitätsklassen wie P und NP durch Erweiterungen der Logik erster Stufe beschrieben werden. Zur Bestimmung der Ausdrucksstärke der relevanten Logiken werden unter anderem Zwei-Personen Spiele behandelt.

Material

Durch Anklicken der einzelnen Kapitel erhalten Sie (zu gegebener Zeit) das Skript zur Vorlesung.

  1. Inhalts- und Literaturverzeichnis, Index
  2. Einführung und Grundlagen
  3. Die Komplexität der Logik erster Stufe
  4. Ehrenfeucht-Fraïssé-Spiele und Lokalität
  5. Existentielle Logik zweiter Stufe und NP
  6. Charakterisierung von Komplexitätsklassen durch Fixpunktlogiken
  7. Infinitäre Logiken und Fixpunktlogiken
  8. Überblick über die Charakterisierungen der Komplexitätsklassen durch Logiken

Das vollständige Skript: als PDF.

Informationen zur Vorlesung und zu den Übungen

Termine:

Art Zeit Ort
Vorlesung   Mo 11-13 Uhr Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1'308
Mi 13-15 Uhr Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1'307
Übung Mi 15-17 Uhr Schrödinger-Zentrum (Rudower Chaussee 26), Raum 1'307

Dozent und Übungsleiter:

André Hernich
Sprechstunde: Di, 14-15 Uhr

Übungsaufgaben

Es gibt regelmäßig Übungsaufgaben, deren erfolgreiche Bearbeitung (mindestens 40% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.

Prüfung

Zu Beginn der Semesterferien finden mündliche Prüfungen statt. Für die Zulassung zur Prüfung müssen mindestens 40% der Punkte in den Übungsaufgaben erworben werden.

Literatur

Die Vorlesung orientiert sich vor allem an den Skripten zur gleichnamigen Vorlesung von Stephan Kreutzer und Nicole Schweikardt im Sommersemester 2005 (PDF-Datei) und von Nicole Schweikardt im Sommersemester 2007.

Ergänzend seien auch folgende Bücher empfohlen:

[EF] H.-D. Ebbinghaus und J. Flum. Finite Model Theory. Springer-Verlag, 1999.
[GKL+] E. Grädel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema und S.Weinstein. Finite Model Theory and Its Applications. Springer-Verlag, 2007.
[I] N. Immerman. Descriptive Complexity. Springer-Verlag, 1999.
[L] L. Libkin. Elements of Finite Model Theory. Springer-Verlag, 2004.

Insbesondere zum letzten Kapitel könnte auch folgender Artikel interessant sein:

[G] M. Grohe. Finite variable logics in descriptive complexity theory. Bulletin of Symbolic Logic 4, S. 345-398, 1998.

zuletzt geändert: 10. Juli 2011
André Hernich