Problemseminar Komplexitätstheorie (WS 2012/13)

Problemseminar aus dem Master-Kernmodul Komplexitätstheorie (10-202-2112)

Überblick

In dem Seminar werden einzelne Themen aus der Komplexitätstheorie behandelt, die aus dem Buch Theory of Computation von Dexter Kozen entnommen sind.

Organisatorisches


Programm

Datum Thema Vortragender Betreuer
1. 14.11.12 Alternation (Kozen, Lecture 7) Tariq Yousef Alexander Kartzow
3. 05.12.12 The polynomial time hierarchy (Kozen, Lecture 9) Mirko Pinseler Alexander Kartzow
4. 12.12.12 More on the polynomial time hierarchy (Kozen, Lecture 10) Georg Richter Alexander Kartzow
5. 19.12.12 Kollabierende Hierarchien (Schöning, Thema 16) Andreas Haselhuhn Markus Lohrey
6. 09.01.13 Probabilistische Algorithmen (Schöning, Teil 1 von Thema 17) Tom Liebmann Markus Lohrey
9. 30.01.13 Graphenisomorphie (Schöning, Thema 18) Robert Rössling Markus Lohrey
2. 28.02.13 Problems complete for PSPACE (Kozen, Lecture 8) Frank Reimann Alexander Kartzow
10. 28.02.13 Zählklassen und der Satz von Toda (Schöning, Thema 19) Sebatian Bulka Markus Lohrey
11. 28.02.13 Zählklassen und der Satz von Toda (Schöning, Thema 19) fällt aus Markus Lohrey
12. 04.03.13 Isomorphie von Bäumen in Logspace (siehe Homepage von Steven Lindell) Felix Kühnl Markus Lohrey
13. 04.03.13 Kommunikationskomplexität I (Wegner, S. 231-245) Danny Richter Markus Lohrey
14. 04.03.13 Kommunikationskomplexität II (Wegner, S. 231-245) Fabian Externbrink Markus Lohrey

Literatur


Impressum
Last modified: Thu Oct 2 19:10:17 CEST 2003