Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.3658
Publisher DOI: | 10.23638/LMCS-17(2:10)2021 | arXiv ID: | 1709.08991 | Title: | Reachability switching games | Language: | English | Authors: | Fearnley, John Gairing, Martin Mnich, Matthias ![]() Savani, Rahul |
Keywords: | Deterministic Random Walks; Model Checking; Reachability; Simple Stochastic Game; Switching Systems | Issue Date: | 22-Apr-2021 | Publisher: | Department of Theoretical Computer Science, Technical University of Braunschweig | Source: | Logical Methods in Computer Science (2021) | Abstract (english): | 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. |
URI: | http://hdl.handle.net/11420/9156 | DOI: | 10.15480/882.3658 | ISSN: | 1860-5974 | Journal: | Logical methods in computer science | Institute: | Algorithmen und Komplexität E-11 | Document Type: | Article | Project: | Multivariate Algorithmen für Scheduling mit hoher Multiplizität | Funded by: | Deutsche Forschungsgemeinschaft (DFG) | 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). | License: | ![]() |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
1709.08991.pdf | Verlags-PDF | 464,54 kB | Adobe PDF | View/Open![]() |
Page view(s)
254
Last Week
0
0
Last month
44
44
checked on Jun 2, 2023
Download(s)
76
checked on Jun 2, 2023
Google ScholarTM
Check
Note about this record
Cite this record
Export
This item is licensed under a Creative Commons License