Seminar Logik, Komplexität, Spiele: Definierbarkeit und Komplexität

SS 2014

Organisation

Die Vorträge finden statt am:

  • Donnerstag, 10. Juli, im Seminarraum 9U09 (E3, Ahornstr. 55)
Die Vorträge können wahlweise auf deutsch oder englisch gehalten werden.

Zeitplan

bis 15.4.Vorbesprechung
30.4.Gliederung
31.5.Ausarbeitung
20.6.Endgültige Fassung
1.7.Folien
10.7.Vorträge

Programm

Donnerstag, 10. Juli
10:0010:30Thomas SchemmerFirst-order logic and circuit complexity
10:3511:05Oliver MajorOn symmetric circuits and fixed-point logics
11:2511:55Friedrich Leonard DahlmannTree canonization and transitive closure
12:0012:30Gustav Leopold GrabolleL-Recursion and a logic for logarithmic space
14:3015:00Tuan Anh NguyenOn finite rigid structures
15:0515:35Marc SeldersLocality of order-invariant first-order formulas

Inhalt

In diesem Seminar sollen Zusammenhänge zwischen logischer Definierbarkeit und algorithmischer Komplexität thematisiert werden. Dabei werden zentrale Methoden und Konzepte der Endlichen Modelltheorie vorgestellt, und Verbindungen zu wichtigen Fragestellungen der algorithmischen Komplexitätstheorie diskutiert.

Die Endliche Modelltheorie untersucht die Eigenschaften und das Verhalten von Logiken (wie z.B. der Prädikatenlogik) die sich ergeben, wenn als mögliche Modelle nur endliche Strukturen betrachtet werden. Klassische Fragestellungen umfassen etwa die relative Ausdrucksstärke verschiedener Logiken untereinander, oder die strukturelle und algorithmische Komplexität von definerbaren Strukturklassen sowie deren asymptotische Wahrscheinlichkeit.

In diesem Seminar wird vor allem das Teilgebiet der deskriptiven Komplexitätstheorie genauer beleuchtet. Ausgangspunkt ist die Frage nach der algorithmischen Komplexität von Entscheidungsproblemen für Logiken auf endlichen Strukturen (z.B. Modelchecking-Problem und Äquivalenz-Problem). Überraschenderweise ergeben sich hierbei starke Zusammenhänge zwischen klassischen Fragestellungen der Logik und wichtigen Problemen der algorithmischen Komplexitätstheorie. Bekannte Beispiele sind die Charakterisierung der Komplexitätsklasse NP durch die existentielle Logik zweiter Stufe, oder die logische (und spieltheoretische) Formulierung eines (für die Praxis sehr bedeutsamen) Algorithmus für das Graphisomorphieproblem.

Folgenden Aspekte werden innerhalb des Seminars genauer thematisiert:

  • Wichtige Werkzeuge der endlichen Modelltheorie, z.B. Ehrenfeucht-Fraïsse Spiele und Lokalitätsbegriffe
  • Die Frage nach einer Logik für Polynomialzeit
  • Logiken für Logspace-Klassen
  • k-Variablen Logik und das Graphisomorphieproblem
  • Die Ausdrucksstärke von Fixpunktlogik mit Zählquantoren
  • Lineare Algebra und logische Definierbarkeit

Für das Seminar sind Kenntnisse aus der Vorlesung Mathematische Logik notwendig; Kenntnisse aus der Vorlesung Algorithmische Modelltheorie sind wünschenswert, aber nicht notwendig.

Themen

ThemaVortragende(r)Betreuer(in)Literatur
Tree canonization and transitive closureFriedrich Leonard DahlmannFaried Abu Zaid[EtIm00]
L-Recursion and a logic for logarithmic spaceGustav Leopold GrabolleWied Pakusa[GrGrHeLa11]
First-order logic and circuit complexityThomas SchemmerSvenja Schalthöfer[Vo99]
On symmetric circuits and fixed-point logicsOliver MajorSvenja Schalthöfer[AnDa14]
On finite rigid structuresTuan Anh NguyenSimon Lessenich[GuSh96]
Order-invariant logicsOliver BösingFrederic Reinhardt[Sc13, Li04]
Locality of order-invariant first-order formulasMarc SeldersFrederic Reinhardt[GrSc00]

Literatur

Zuordnung

  • Informatik (B.Sc.)/Seminar Informatik
  • Mathematik (B.Sc.)/Seminar: Logik, Komplexität, Spiele
  • Informatik (M.Sc.)/Seminar Theoretische Informatik
  • Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)
  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/Modul Algebra
  • Mathematik (S II)/Hauptstudium/Modul Angewandte Mathematik

Voraussetzungen

  • Modul Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Simon Lessenich, Faried Abu Zaid, Wied Pakusa, Frederic Reinhardt