Fearnley, JohnJohnFearnleyGairing, MartinMartinGairingMnich, MatthiasMatthiasMnichSavani, RahulRahulSavani2021-03-252021-03-252021-04-22Logical Methods in Computer Science (2021)http://hdl.handle.net/11420/9156We study the problem of deciding the winner of reachability switching games for zero-, one-, and two-player variants. Switching games provide a deterministic analogue of stochastic games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP \ 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 the switching variant of a game is harder in complexity-theoretic terms than the corresponding stochastic version.en1860-597420212129Department of Theoretical Computer Science, Technical University of Braunschweighttps://creativecommons.org/licenses/by/4.0/Deterministic Random WalksModel CheckingReachabilitySimple Stochastic GameSwitching SystemsMathematikJournal Article10.15480/882.365810.23638/LMCS-17(2:10)202110.15480/882.36581709.08991Journal Article