Subexponential algorithms for solving parity games

Marcin Jurdziński
Universty of Warwick, United Kingdom
Friday, 15 December, 2006 (All day)

Deciding the winner in a parity game is polynomial time equivalent to checking if a formula of the modal logic with fixpoint operators (aka. the modal mu-calculus) holds in a state of a Kripke structure. The exact computational complexity of the problem is an intriguing open problem: it is known to be in UP (unambiguous NP) and co-UP, but no polynomial time algorithm is known. This talk surveys a few recent algorithmic ideas which yield improved running time bounds for the problem. One is obtained by a reduction of parity games to the problem of finding the unique sink in a "unique sink orientation" of a hypercube and it yields a subexponential randomized algorithm. The other is a modification of a classical recursive algorithm for solving parity games that originates from the work of McNaughton and Zielonka and it yields a subexponential deterministic algorithm.