2026-07-22T11:54:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9128 2024-03-06T10:43:26Z ddc:004 open_access

Reachability Switching Games Fearnley, John Gairing, Martin Mnich, Matthias Savani, Rahul Deterministic Random Walks Model Checking Reachability Simple Stochastic Game Switching Systems In this paper, we study the problem of deciding the winner of reachability switching games. We study zero-, one-, and two-player variants of these 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 n coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. We also study the structure of winning strategies in these games, and in particular we show that exponential memory is required in both the one- and two-player settings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John Fearnley and Martin Gairing and Matthias Mnich and Rahul Savani 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.124 urn:nbn:de:0030-drops-91282 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.124 eng https://creativecommons.org/licenses/by/3.0/legalcode