Evènement pour le groupe Séminaire Méthodes Formelles

Date 2016-05-31  11:00-12:00
TitreThe Complexity of All-switches Strategy Improvement 
RésuméWe study all-switches strategy improvement algorithms for parity, mean-payoff, discounted-payoff, and simple stochastic games. While these algorithms are now known to take exponential time in the worst case, we follow a recent line of work on the simplex method, and study them from a computational complexity point of view. We show that it is PSPACE-complete to decide the following problems: (1) given an edge e, will all-switches strategy improvement ever switch e? (2) given an edge e, is e in the optimal strategy found by all-switches strategy improvement? 
OrateurJohn Fearnley 
UrlUniversity of Liverpool 

Aucun document lié à cet événement.

Retour à l'index