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 Di, 14-16 Uhr, zoom. Beginn voraussichtlich am 12.10.
Übung 14-tägig, voraussichtlich Do 10-12, ab 4.11.
Querverbindungen Komplexitätstheorie, Logik
Voraussetzungen GTI-Stoff wird vorausgesetzt,
Komplexitätstheorie ist hilfreich, aber nicht unbedingt notwendig
Forschungsbereich (MPO) Algorithmen und Komplexität
Materialien Moodle-Arbeitsraum
 Sprache  Folien und Videos: Englisch, Webinar: deutsch/englisch

 

 

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

 

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

Ein Folienskript wird parallel zur Vorlesung erstellt.

Weitere Literatur:

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