Parity games in weak arithmetic theories

Speaker(s)

Leszek Kołodziejczyk

Affiliation

Uniwersytet Warszawski

Date

Dec. 3, 2008, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Parity games in weak arithmetic theories I will present A. Beckmann and F. Moller's paper "On the complexity of parity games". The main result of the paper is that positional determinacy of parity games can be proved in a weak subtheory of Peano Arithmetic called S^2_2. The provability of determinacy in a still weaker theory, S^1_2, would mean that the problem of deciding which player wins from a given position in a parity game is in P. The current result implies that the problem of finding a winning strategy is in the class PLS (polynomial local search).

---