Arbeitsgruppe Theoretische Informatik

Die Komplexität von Paritätsspielen

Ansprechpartner: Fabian Müller, Oliver Woizekowski

Ziel der Arbeit ist es, den Beweis, dass das Bestimmen eines Siegers in einem Paritätsspiel in UP liegt, aufzuarbeiten. Dabei erläutern Sie Paritätsspiele und die Klassen UP und co-UP. Darüber hinaus können Sie weitere Probleme in UP identifizieren oder Varianten von Paritätsspielen analysieren.

Quellen

  1. http://www.lsv.ens-cachan.fr/~doyen/mpri/Jurdzinski-UPcoUP.pdf