Problemseminar Komplexitätstheorie (WS 2007/08)

Organisatorisches


Programm (die Themen 1-9 finden Sie im Buch von U. Schöning)

Datum Thema Vortragender
1. LOGSPACE, Zufallsirrfahrten auf Graphen und universelle Durchlaufsequenzen fällt aus
2. Äquivalenzprobleme und untere Schranken bei Branching-Programmen fällt aus
4. 5.12 Untere Schranken für die Paritätsfunktion Christian Holzmüller
5. 12.12 Exponentielle untere Schranke für die Länge von Resolutionsbeweisen Jan Demter
6. 19.12 Kollabierende Hierarchien Niko Haubold
7. 9.1 Probabilistische Algorithmen, Wahrscheinlichkeitsverstärkung und Recycling von Zufallszahlen Sven Krosse
8. 16.1 Der BP-Operator und Graphenisomorphie Johannis Zschache
9. 23.1 Der BP-Operator und die Mächtigkeit von Zählklassen Stefan Göller
10. 30.1 Geography ist PSPACE-vollständig (Papadimitriou, Seite 455-462) Michael Lühr
11. Go ist PSPACE-vollständig (Papadimitriou, Seite 462-469) fällt aus
12. Tetris ist NP-vollständig

Lehrbücher


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