The complexity of request-response games - Chatterjee, Krishnendu; Henzinger, Thomas A; Horn, Florian; Dediu, Adrian-Horia; Inenaga, Shunsuke; Martín-Vide, Carlos; LATA: Language and Automata Theory and Applications (Tarragona, Spain : Springer, 2011)
We consider two-player graph games whose objectives are request-response condition, i.e conjunctions of conditions of the form "if a state with property Rq is visited, then later a state with property Rp is visited". The winner of such games can be decided in EXPTIME and the problem is known to be NP-hard. In this paper, we close this gap by showing that this problem is, in fact, EXPTIME-complete. We show that the problem becomes PSPACE-complete if we only consider games played on DAGs, and NP-complete or PTIME-complete if there is only one player (depending on whether he wants to enforce or spoil the request-response condition). We also present near-optimal bounds on the memory needed to design winning strategies for each player, in each case.
published
yes
Keywords: conference paper