Zum Inhalt
Fakultät für Informatik

Logik und Komplexität

Veranstaltungsnummer 042617
Titel Logik und Komplexität (INF-MSC-509)
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Vertiefungsmodul (MPO)
Semester Wintersemester 2021/22
SWS 4 (3V+1Ü)
Kreditpunkte 6
Ort und Zeit Webinar: Dienstags, 14:00 - 16:00 Uhr (Beginn: 12.10.2021)
Übung 14-tägig, voraussichtlich Donnerstags 10:00 - 12:00 (Beginn: 04.11.2021)
Querverbindungen Komplexitätstheorie, Logik
Voraussetzungen GTI-Stoff wird vorausgesetzt,
Komplexitätstheorie ist hilfreich, aber nicht unbedingt notwendig
Forschungsbereich (MPO) Algorithmen und Komplexität
Materialien Im Moodle-Arbeitsraum (Anmeldung über LSF)
Sprache Folien und Videos: Englisch, Webinar: deutsch/englisch

Aktuelles

The course will be taught online and at least partially in English. It will combine synchonous and asynchronous elements:

  • Slides in English, covering all content
  • Videos in English, for some of the content
  • "Webinars" in English and/or German depending on the participants (if everybody speaks German, which is quite likely, they will probably be in German)

 

Die Veranstaltung wird voraussichtlich virtuell und zu einem großen Teil auf Englisch stattfinden. Sie kombiniert dabei synchrone und asynchrone Elemente:

  • Englischsprachige Foliensätze für alle Inhalte
  • Englischsprachige Videos für einige Inhalte
  • Webinars in deutscher und/oder englischer Sprache nach Absprache mit den Teilnehmer:innen

Inhalt

Many algorithmic problems can be described by logical formulae. There is a close connection between the complexity of the formulae and the computational complexity of the problems. This connection plays a role in various areas of (theoretical) computer science, for example in the theory of formal languages, database theory, complexity theory and in the context of automatic verification. The lecture will deal with important such correspondence results and with the basic properties of the logics involved.

Individual topics:

  • Foundations of first-order logic
  • Expressive power of first-order logic: Ehrenfeucht games, locality, other methods
  • Logic and complexity theory: second-order logic, fixed-point logics, separations
  • Evaluation of logical formulae: Algorithms and complexity
  • Logic and Formal Languages
  • Efficient logics

 

Viele algorithmische Probleme lassen sich durch logische Formeln beschreiben. Dabei besteht ein enger Zusammenhang zwischen der Kompliziert der Formeln und der Berechnungskomplexität der Probleme. Dieser Zusammenhang spielt in verschiedenen Bereichen der (theoretischen) Informatik eine Rolle, zum Beispiel in der Theorie Formaler Sprachen, der Datenbanktheorie, der Komplexitätstheorie und im Zusammenhang automatischer Verifikation. Die Vorlesung wird sich mit wichtigen solchen Korrespondenz-Resultaten und mit den grundlegenden Eigenschaften der beteiligten Logiken beschäftigen.

Einzelthemen:

  • Logik erster Stufe: Grundlagen
  • Ausdrucksstärke der Logik erster Stufe: Ehrenfeuchtspiele, Lokalität, andere Methoden
  • Logik und Komplexitätstheorie: Logik zweiter Stufe, Fixpunktlogiken, Trennungen
  • Auswertung logischer Formeln: Algorithmen und Komplexität
  • Logik und Formale Sprachen
  • Logik und Verifikation

Literatur

Ein Folienskript wird parallel zur Vorlesung erstellt.

Weitere Literatur:

  • Leonid Libkin: Elements of Finite Model Theory, Springer, 2004
  • Immerman: Descriptive Complexity, Springer, 1999