Reachability switching games

Fearnley, J, Gairing, M ORCID: 0000-0002-0569-7113, Mnich, M and Savani, R ORCID: 0000-0003-1262-7831 (2018) Reachability switching games .

Text 1709.08991v1.pdf - Published version Download (224kB)

Description

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 ∩ 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.

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:	22 Apr 2026 04:55
DOI:	10.4230/LIPIcs.ICALP.2018.124
Related Websites:	Author Item URL
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3009773
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.