Logik in der Informatik Prof. Dr. Martin Grohe

Aktuelles

Die erste Sitzung des Seminars mit Einführung und Vergabe der Vortragsthemen findet am Freitag dem 13. April statt.

Einführung

Es besteht eine enger Zusammenhang zwischen der Komplexität algorithmischer Probleme, also dem Aufwand an Ressourcen wie Zeit oder Speicherplatz, die zu ihrer Lösung erforderlich sind, und ihrer Beschreibungskomplexität, also dem Aufwand an sprachlich-logischen Ressourcen, die zur ihrer Beschreibung in einem formalen logischen System erforderlich sind. Sprich: Probleme, die einfach algorithmisch lösbar sind, sind einfach zu beschreiben und umgekehrt. Dieser Zusammenhang hat zu verschiedenen logischen Charakterisierungen aller gängigen Komplexitätsklassen geführt. In diesem Seminar wollen wir uns mit einer Reihe solcher Charakterisierungen beschäftigen, die "beweistheoretischer" Natur sind. (Die Beweistheorie ist ein Teilbereich der mathematischen Logik, dessen Grundlagen wir ebenfalls in dem Seminar erarbeiten werden.)

Zeit und Raum

Freitags 09 - 11 Uhr im Erwin Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'307

Dozent

Prof. Dr. Martin Grohe
Sprechstunde im SS12: Donnerstags 15-16 Uhr

Literatur

[B1]	Samuel R. Buss, An Introduction to Proof Theory. Chapter I of Samuel R. Buss, Handbook of Proof Theory, Elsevier 1998.
[B2]	Samuel R. Buss, First-Order Proof Theory of Arithmetic. Chapter II of Samuel R. Buss (ed.), Handbook of Proof Theory, Elsevier 1998.
[CN]	Stephen Cook and Phuong Nguyen, Logical Foundations of Proof Complexity (pdf), Cambridge University Press 2010.

Vorträge

Sitzung 1 (20.4.2012)

[CN] Kap. 2A (S.7-15)

 

Sitzung 2 (27.4.2012)

[CN] Kap. 2B (S.15-29)

 

Sitzung 3 (4.5.2012)

[CN] Kap. 2C-2E, 3A (S.29-42)

 

Sitzung 4 (11.5.2012)

[CN] Kap. 3B-3C.2 (S.42-57)

 

Sitzung 5 (25.5.2012)

[CN] Kap. 3C.2-3D, 4A-4B (S.57-67, 71-78)

 

Sitzung 6 (8.6.2012)

[CN] Kap. 4C-4E (S.78-90)

 

Sitzung 7 (15.6.2012)

[CN] Kap. 5A-5D (S.91-107)
Maria Tammik

 

Sitzung 8 (22.6.2012)

[CN] Kap. 5E-5G (S.108-126)
Jennifer Gehrke

 

Sitzung 9 (6.7.2012)

[CN] Kap. 6A-6B (S.127-136)
Wilhelm Becker

 

Sitzung 10 (13.7.2012)

[CN] Kap. 6C-6D (S.136-150)
Pietro Fornara