Subexponential algorithms for solving parity games

Prelegent(ci)

Marcin Jurdziński

Afiliacja

Uniwersytet Warszawski

Termin

23 listopada 2006 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Solving parity games is polynomial time equivalent to the modal mu-calculus model checking problem and its exact computational complexity 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.

---