Options
Reachability switching games
Citation Link: https://doi.org/10.15480/882.3658
Publikationstyp
Journal Article
Date Issued
2021-04-22
Sprache
English
Institut
TORE-DOI
TORE-URI
Volume
17
Issue
2
Start Page
1
End Page
29
Citation
Logical Methods in Computer Science (2021)
Publisher DOI
Scopus ID
ArXiv ID
Publisher
Department of Theoretical Computer Science, Technical University of Braunschweig
We 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.
Subjects
Deterministic Random Walks
Model Checking
Reachability
Simple Stochastic Game
Switching Systems
DDC Class
510: Mathematik
Funding Organisations
More Funding Information
Fearnley wurde unterstützt durch den EPSRC Grant EP/P020909/1 \Solving Parity Games in Theory und Praxis". Mnich wurde unterstützt durch ERC Starting Grant 306465 (BeyondWorstCase).
Publication version
publishedVersion
Loading...
Name
1709.08991.pdf
Size
464.54 KB
Format
Adobe PDF