Springe zum Hauptinhalt
Theoretische Informatik
Theoretische Informatik
Theoretische Informatik 

Pro- und Hauptseminar im Wintersemester 2026/27 - Themen und Termine

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. Aus dem TU-Netz sollten Sie Zugriff auf die elektronische Version haben.
  • Easley and Kleinberg, Networks, Crowds, and Markets.

Vollständige Probleme für andere Klassen als NP. 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

Einführung (Dominik Scheder, 3. Dezember 2026)

Sokoban (Henry Meisel, 10. Dezember 2026). 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. Sokoban is PSPACE-complete von Joseph C. Culberson.

Quantified SAT (Gilles Werner, 10. Dezember 2026). Dies ist die vielleicht grundlegendste Reduktion in PSPACE. Der Trick ist, eine potentiell exponentiell lange Berechnung in ein kurzes Spiel einzufangen.

Go (Luis Kirste, 17. Dezember 2026). Das Brettspiel Go spielt man üblicherweise auf einem 19x19-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.

#2-SAT is vollständig für #P (Frieder Petzold, 17. Dezember 2026). Bisher kannte man nur sehr komplizierte Beweise. Seit diesem Jahr gibt's einen viel einfacheren: A Novel Reduction from #SAT to #2SAT Based on Symmetry: Simply Drop the Large Clauses von Bannach, Demaine, Gomez, and Hecher. Das Paper schaut kompliziert aus, der Beweis ist im Endeffekt gar nicht soooo schwierig. Trotzdem eher was fürs Hauptseminar, würde ich sagen.

Algorithmische Spieltheorie und Mechanismus-Design

von Neumanns Minmax-Theorem und Nashs Theorem (Felix Noack, 7. Januar 2027). Ausgangspunkt: Kapitel 1 von Algorithmic Game Theory.

Theorie wiederholter Spiele (Merlin Trommer, 7. Januar 2027).

Routing Games (Leon Pascal Lormis, 14. Januar 2027). Ausgangspunkt: Kapitel 18 von Algorithmic Game Theory

Market Clearing (Tristan Arnold, 14. Januar 2027). Ausgangspunkt: Kapitel 5 in Algorithmic Game Theory, oder auch Hajiaghayis Vorlesungsskript, 2010 und gerne auch einfach Wikipedia, zum Beispiel über den Fisher market.

Trading Games: Markets with Intermediaries (Natalie Berndt, 21. Januar 2027) Ausgangspunkt: Kapitel 11 (vielleicht auch 10) aus Networks, Crowds, and Markets

Kooperative Spieltheorie (Markus Schmidt, 21. Januar 2027). Ausgangspunkte: John C.S. Luis Folien, Wikipedia, vielleicht auch Kapitel 15 aus Algorithmic Game Theory.

Kombinatorische Auktionen: Der Vickrey-Clarke-Groves-Mechanismus (Florian Kunze, 28. Januar 2027). Ausgangspunkt: Kapitel 9.3, 9.5 und 11 von Algorithmic Game Theory.