Parity games in weak arithmetic theories

Prelegent(ci)

Leszek Kołodziejczyk

Afiliacja

Uniwersytet Warszawski

Termin

3 grudnia 2008 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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).

---