文章基本信息

标题：Reachability Switching Games
本地全文：下载
作者：Savani, Rahul ; Mnich, Matthias ; Gairing, Martin 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2021
卷号：17
期号：2
页码：1-29
语种：English
出版社：Technical University of Braunschweig
摘要：We study the problem of deciding the winner of reachability switching gamesfor zero-, one-, and two-player variants. Switching games provide adeterministic analogue of stochastic games. We show that the zero-player caseis NL-hard, the one-player case is NP-complete, and that the two-player case isPSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardnessfor a succinctly-represented model that maintains the upper bound of NP $\cap$coNP. For the one- and two-player cases, our results hold in both the natural,explicit model and succinctly-represented model. Our results show that theswitching variant of a game is harder in complexity-theoretic terms than thecorresponding stochastic version.
关键词：Computer Science - Formal Languages and Automata Theory; Computer Science - Computer Science and Game Theory; Computer Science - Logic in Computer Science