Masterarbeit MSTR-2018-106

Bibliograph.
Daten
Naghibi, Youssof: Paritätsspiele in quasipolynomieller Zeit.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Masterarbeit Nr. 106 (2018).
77 Seiten, deutsch.
Kurzfassung

Die im 1. Kapitel vorgestellten Resultate stammen aus [1, S. 135-151] und dienen der grundlegenden Einführung von Zwei-Spieler-Spielen, die wir im Folgenden betrachten werden. Das Hauptergebnis in diesem Kapitel ist, dass es in Paritätsspielen bei festem Startknoten für einen Spieler eine gedächtnislose Gewinnstrategie gibt. Die Kapitel 2 bis 4 basieren hauptsächlich auf der Arbeit von [2]. Im zweiten Kapitel beschäftigen wir uns dabei mit Algorithmen zur Lösung von Paritätsspielen, d.h. zur Entscheidung welcher Spieler eine Gewinnstrategie in Paritätsspielen besitzt. Zunächst werden wir beweisen, dass es zur Lösung von Paritätsspielen einen alternierenden Algorithmus mit polylogarithmischen Speicher gibt. Dazu wird dieser Algorithmus eine sogenannte Gewinnstatistik verwenden. Basierend auf der Gewinnstatistik lassen sich auch Algorithmen mit quasipolynomiellen Laufzeiten in O (ncdlog(m)e) zur Lösung von Paritässpielen herleiten, indem wir die Funktionsweise des alternierenden polylogarithmischen Algorithmus ausnutzen. Zudem werden wir feststellen, dass Paritätsspiele (und somit auch Mullerspiele) FPT-Probleme sind ("fixed parameter tractables"). Im 3. Kapitel beschäftigen wir uns mit (gefärbten) Mullerspielen und dazu äquivalente Paritätsspiele. Wir werden zeigen, dass es unter bestimmten Voraussetzungen auch in Mullerspielen für jeden Spieler mit einer Gewinnstrategie eine gedächtnislose Gewinnstrategie gibt. Im 4. Kapitel werden wir einen Zusammenhang zwischen Dominating Set-Problemen und dem Lösen von Muller- und (mehrdimensionalen) Paritätsspielen herstellen, um zu zeigen, dass bestimmte Laufzeiten zur Lösung dieser Spiele vermutlich nicht möglich sind, was widerum auf der Vermutung FPT6=W[1] beruht. Im 5. Kapitel stellen wir den Zusammenhang zwischen Mean-Payoff-Spielen und Paritätsspielen her. Dabei zeigen wir unter anderem, dass (diskontierte) Mean-Payoff-Spiele so wie Paritätsspiele gedächtnislos sind, d.h. dass aus der Existenz einer Gewinnstrategie die Existenz einer gedächtnislose Gewinnstrategie folgt. Außerdem werden wir zeigen, dass Paritätsspiele sich auf (diskontierte) Mean-Payoff-Spiele reduzieren lassen können, womit wir das Hauptresultat erhalten, dass diese Spiele und somit auch Paritätsspiele in UP\Co-UP sind.

Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
BetreuerDiekert, Prof. Volker
Eingabedatum18. Dezember 2019
   Publ. Informatik