
Evènement pour le groupe Séminaire Méthodes Formelles
Date  20190312 11:0012:00 
Titre  The complexity of mean payoff games using universal graphs 
Résumé  We study the computational complexity of solving mean payoff games. This class of games can be seen as an extension of parity games, and they have similar complexity status: in both cases solving them is in NP and coNP and not known to be in P. In a breakthrough result Calude, Jain, Khoussainov, Li, and Stephan constructed in 2017 a quasipolynomial time algorithm for solving parity games, which was quickly followed by two other algorithms with the same complexity. Our objective is to investigate how these techniques can be extended to the study of mean payoff games. We construct two new algorithms for solving mean payoff games. Our first algorithm depends on the largest weight N (in absolute value) appearing in the graph and runs in sublinear time in N, improving over the previously known linear dependence in N . Our second algorithm runs in polynomial time for a fixed number k of weights. 
Lieu  178 
Orateur  Nathanaël Fijalkow 
Url  CNRS, LaBRI 
Aucun document lié à cet événement. RetourRetour à l'index
 