Pro- und Hauptseminar im Wintersemester 2026/27 - Themenvorschläge
Die beiden großen Themenbereiche des Hauptseminars sind Reduktionen in- und außerhalb von NP sowie Spieltheorie und Mechanism Design
Literatur
- Christos Papadimitriou, Complexity Theory
- Sanjeev Arora und Boaz Barak, Computational Complexity, a Modern Approach
- Noam Nisan, Tim Roughgarden, Éva Tardos und Vijay V. Vazirani (Herausgeber), Algorithmic Game Theory
PSPACE-Vollständigkeit. NP-vollständige Probleme wirken häufig wie kombinatorische Puzzlespiele. Bei PSPACE ist das anders: viele von Ihnen haben den Charakter eines Zweipersonenspieles wie Schach oder Go. Hier stellen Sie
Quantified SAT. Dies ist die vielleicht grundlegendste Reduktion in PSPACE. Der Trick ist, eine potentiell exponentiell lange Berechnung in ein kurzes Spiel einzufangen.
Go. Das Brettspiel Go spielt man üblicherweise auf einem $19\times 19$-Brett. Rein theoretisch kann man auch Positionen auf einem größeren Brett betrachten und sich fragen, ob Weiß eine Gewinnstrategie hat. Dieses Problem ist PSPACE-vollständig.
Sokoban. Das Spiel Sokoban ist ein japanisches Videospiel aus den 1980-Jahren. Man muss in einem Lagerraum Kisten auf bestimmte Zielpositionen schieben. Allerdings kann man immer nur eine Kiste schieben (zwei gleichzeitig, das wäre zu schwer) und kann keine Kiste ziehen. Kann der tapfere Lagerverwalter alle Kisten auf die vorgesehenen Zielpositionen schieben?
Der sehr unterhaltsame PSPACE-Vollständigkeitsbeweis zeigt im Prinzip, wie man ein Sokoban-Puzzle so baut, dass der Lagerverwalter eine Computerberechnung simulieren muss und dabei eigentlich gar keine große Entscheidungsfreiheit hat.
Reguläre Grammatiken. Sei $G$ eine reguläre Grammatik. Kann $G$ jedes Wort ableiten oder gibt es ein Wort $w \in \Sigma^*$ mit $w \not \in L(G)$ In Theoretische Informatik II haben Sie wahrscheinlich gelernt, dass alles, was mit regulären Sprachen zu tun hat, "einfach" ist. Aber so einfach ist es nun mal nicht. Das gerade beschriebene Problem ist tatsächlich PSPACE-vollständig, auch wenn es auf den ersten Blick nicht so aussieht!
Algorithmische Spieltheorie und Mechanismus-Design
von Neumanns Minmax-Theorem und Nashs Theorem
Vickry-Auktionen
Das mit den Aufträgen, den Koalitionen und der Preisverteilung (Keinen Titel oder Referenz im Kopf. Johannes fragen)
