Paper by Erik D. Demaine
- Reference:
- Hayashi Ani, Erik D. Demaine, Della Hendrickson, and Jayson Lynch, “Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets”, Theoretical Computer Science, volume 969, 2023, pages 113945.
- Abstract:
-
We analyze the computational complexity of motion planning through local
“input/output” gadgets with separate entrances and exits, and a
subset of allowed traversals from entrances to exits, each of which changes
the state of the gadget and thereby the allowed traversals. We study such
gadgets in the zero-, one-, and two-player settings, in particular extending
past motion-planning-through-gadgets work [DGLR18, DHL20] to zero-player games
for the first time, by considering “branchless” connections
between gadgets that route every gadget's exit to a unique gadget's entrance.
Our complexity results include containment in L, NL, P, NP, and PSPACE; as
well as hardness for NL, P, NP, and PSPACE. We apply these results to show
PSPACE-completeness for certain mechanics in the video games Factorio, [the
Sequence], and a restricted version of Trainyard, improving the result of
[ALP18a]. This work strengthens prior results on switching graphs,
ARRIVAL [DGK+17], and reachability switching games [FGMS21].
- Comments:
- This paper is also available from ScienceDirect and as arXiv:2005.03192.
- Length:
- The paper is 42 pages.
- Availability:
- The paper is available in PDF (16334k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- GadgetsIO_WALCOM2022 (Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.