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 17 (2): 1-29 (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