Fearnley, J, Gairing, M 
ORCID: 0000-0002-0569-7113, Mnich, M and Savani, AR
(2021)
Reachability switching games.
Logical Methods in Computer Science, 17 (2).
pp. 10-29.
ISSN 1860-5974
Abstract
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.
| Item Type: | Article |
|---|---|
| Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 23 Dec 2021 16:27 |
| Last Modified: | 07 Jun 2025 18:41 |
| DOI: | 10.23638/LMCS-17(2:10)2021 |
| Open Access URL: | https://lmcs.episciences.org/7392 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3145991 |
Altmetric
Altmetric