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”, in Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), edited by Petra Mutzel, Md. Saidur Rahman, and Slamin, Lecture Notes in Computer Science, volume 13174, Jember, Indonesia, March 24–26, 2022, pages 187–198.

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 [3, 4] 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 Factorio, [the Sequence], and a restricted version of Trainyard, improving the result of [1]. This work strengthens prior results on switching graphs, ARRIVAL [5], and reachability switching games [6].

Comments:

This paper is also available as arXiv:2005.03192 and from SpringerLink.

Availability:

The paper is available in PDF (338k).

See information on file formats.

[Google Scholar search]

Related papers:

GadgetsIO_TCS (Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets)