Problemseminar Komplexitätstheorie (WS 2009/10)

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
1. 17.12.09 Alternation (Lecture 7) Wang Jing
2. Problems complete for PSPACE (Lecture 8)
3. The polynomial time hierarchy (Lecture 9)
4. More on the polynomial time hierarchy (Lecture 10)
5. Parallel complexity (Lecture 11)
6. Relations of NC to time-space classes (Lecture 12)
7. 07.01.10 Probabilistic complexity (Lecture 13) und BPP ⊆ ∑2p ∩ ∏2p (Lecture 14) Martin Huschenbett
9. 14.01.09 Probabilistically Checkable Proofs (Lecture 18) Alexander Bach
10. 21.01.09 NP ⊆ PCP(n³,1) (Lecture 19) Christian Mathissen
11. 28.01.09 More in PCP (Lecture 20) Markus Lohrey
12. Unique Satisfiability (Lecture F)
13. Toda's Theorem (Lecture G)

Literatur


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