Fearnley, John, Gairing, Martin 
ORCID: 0000-0002-0569-7113, Mnich, Matthias and Savani, Rahul ORCID: 0000-0003-1262-7831
(2017)
Reachability Switching Games.
.
![[thumbnail of 1709.08991v1.pdf]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
1709.08991v1.pdf - Published version Download (224kB) |
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 $\cap$ 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: | Other |
|---|---|
| Uncontrolled Keywords: | cs.FL, cs.FL, cs.GT, cs.LO |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 05 Oct 2017 06:49 |
| Last Modified: | 07 Jun 2024 07:08 |
| DOI: | 10.4230/LIPIcs.ICALP.2018.124 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3009773 |
Altmetric
Altmetric
