Diese Vorlesung behandelt die neuen bahnbrechenden Entwicklungen im Bereich der Paritätsspiele. Paritätsspiele sind ein grundlegendes Werkzeug für reaktive Programsynthese. Bei reaktiver Programsynthese besteht das Ziel darin, ein Programm zu generieren, das trotz der Aktionen einer gegnerischen Umgebung Fehler vermeidet. Um so ein Programm zu generieren, modellieren wir das Zusammenspiel von dem Programm und der Umgebung als Spiel für zwei Spieler, und dann "lösen" wir das Spiel. Das heißt, dass wir nach einer Strategie suchen, die den Gewinn garantiert. Im Rahmen dieser Vorlesung interessieren wir uns nur für Spiele mit perfekter Information. Dies sind Spiele, wie z.B. Schach, bei denen beide Spieler volle Information über den aktuellen Zustand der Spiele haben. Paritätsspiele bilden eine fundamentale Subklasse von Spielen mit perfekter Information. Sie können komplexe Gewinnbedingungen ausdrücken (z.B. "Spieler A besucht Region W unendlich oft"), und erlauben dabei eine relativ effiziente algorithmische Behandlung.
Die genaue Komplexität von Paritätsspielen ist ein großes ungelöstes Problem der Theoretischen Informatik. Obwohl es bewiesen ist, dass das Problem im Schnitt der Komplexitätsklassen NP und coNP liegt, konnte noch nicht gezeigt werden, dass das Problem in P liegt. In dieser Vorlesung, untersuchen wir Paritätsspiele, und zielen darauf ab, ein in sich geschlossenes Verständnis der jüngsten bahnbrechenden Ergebnissen zu entwickeln, die zeigen dass das Problem in Zeit nO(log(n)) lösbar ist.
Die Übungsblätter werden hier veröffentlicht. Das erste Blatt wird am 30.10.2024 veröffentlicht. Das Abgabedatum von einem Übungsblatt wird auf dem Übungsblatt bekanntgegeben. Die Bearbeitungszeit von einem Übungsblatt beträgt aber, in der Regel, eine Woche. Bitte Ihre Lösungen vor der Übung (am Abgabedatum) abgeben. Email Abgaben an e.keskin@tu-bs.de (als PDF) werden auch akzeptiert. Die Abgabe ist allein oder in Zweiergruppen möglich.
Diese Vorlesung hat als Ziel, die neuen Techniken zum Lösen von Paritätsspielen zu verstehen. Es gibt Material von den vergangenen Semestern, die hilfreich sein können, um die Grundlagen zu verstehen.
Allerdings enthält diese Vorlesung neue Themen, die nur in den handschriftlichen Notizen zu finden sind. Diese werden im Laufe des Semesters hier veröffentlicht.
Die Vorlesung wurde auf folgende Papers und Bücher basiert. Diese Liste ist noch WIP, und wird vervollständigt.