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

Veranstalter: Prof. Dr. Markus Lohrey (Raum 4.37, Tel. 0341-97-32201)
Termin: Donnerstag, 9:15-10:45, im SG 313
Einführungstermin: Donnerstag, 14. Oktober, 9:15, im SG 313

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 ⊆ ∑₂^p ∩ ∏₂^p (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

Sanjeev Arora und Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press 2009
Dexter Kozen: Theory of Computation. Springer 2006
Christo H. Papadimitriou: Computational complexity. Addison-Wesley, 2005
Ingo Wegener: Komplexitätstheorie. Grenzen der Effizienz von Algorithmen. Springer 2003

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