Problemseminar Komplexitätstheorie (WS 2011/12)

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. 24.11.2011 Alternation (Kozen, Lecture 7) Zhu, Xuzhi Markus Lohrey
2. 01.12.2011 Problems complete for PSPACE (Kozen, Lecture 8) Simon Beyer Markus Lohrey
3. 08.12.2011 The polynomial time hierarchy (Kozen, Lecture 9) Chaohui Xia Markus Lohrey
4. More on the polynomial time hierarchy (Kozen, Lecture 10)
5. Kollabierende Hierarchien (Schöning, Thema 16)
6. 05.01.2011 Probabilistische Algorithmen (Schöning, Teil 1 von Thema 17) Sascha Haseloff Markus Lohrey
7. 12.01.2011 Recycling von Zufallszahlen (Schöning, Teil 2 von Thema 17) Sascha Haseloff Markus Lohrey
8. 19.01.2011 Graphenisomorphie (Schöning, Thema 18) Sascha Ludwig Alexander Kartzow
9. 26.01.2011 Graphenisomorphie (Schöning, Thema 18)
10. Zählklassen und der Satz von Toda (Schöning, Thema 19)
11. Zählklassen und der Satz von Toda (Schöning, Thema 19)
12. 02.02.2011 Isomorphie von Bäumen in Logspace (siehe Homepage von Steven Lindell) Fabian Externbrik Alexander Kartzow

Literatur


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