Problemseminar Komplexitätstheorie (WS 2010/11)

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. Alternation (Kozen, Lecture 7)
2. 06.01.2011 Problems complete for PSPACE (Kozen, Lecture 8) fällt aus
3. 13.01.2011 The polynomial time hierarchy (Kozen, Lecture 9) Dirk Albrecht Markus Lohrey
4. More on the polynomial time hierarchy (Kozen, Lecture 10)
5. 20.01.2011 Parallel complexity (Kozen, Lecture 11) Sascha Haseloff Markus Lohrey
6. Relations of NC to time-space classes (Kozen, Lecture 12)
7. 27.01.2011 Probabilistic complexity (Lecture 13) und BPP ⊆ ∑2p ∩ ∏2p (Kozen, Lecture 14) Sebastain Volke Markus Lohrey
8. 03.02.2011 Probabilistically Checkable Proofs (Kozen, Lecture 18) Jörg Dreier Markus Lohrey
9. NP ⊆ PCP(n³,1) (Kozen, Lecture 19)
10. More in PCP (Kozen, Lecture 20)
11. zu vereinbaren Unique Satisfiability (Kozen, Lecture F) Christoph Kämpf Christian Mathissen
12. zu vereinbaren Toda's Theorem (Kozen, Lecture G) Christoph Kämpf Christian Mathissen

Literatur


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