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.

BibTeX

@Article{GadgetsIO_TCS,
  AUTHOR        = {Hayashi Ani and Erik D. Demaine and Della Hendrickson and Jayson Lynch},
  authororig    = {Joshua Ani and Erik D. Demaine and Dylan Hendrickson and Jayson Lynch},
  TITLE         = {Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets},
  JOURNAL       = {Theoretical Computer Science},
  journalurl    = {https://www.journals.elsevier.com/theoretical-computer-science},
  VOLUME        = 969,
  PAGES         = {113945},
  YEAR          = 2023,

  withstudent   = 1,
  replaces      = {GadgetsIO_WALCOM2022},
  papers        = {GadgetsIO_WALCOM2022},
  doi           = {https://dx.doi.org/10.1016/J.TCS.2023.113945},
  dblp          = {https://dblp.org/rec/journals/tcs/AniDHL23},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.1016/j.tcs.2023.113945">ScienceDirect</A> and as <A HREF="https://arxiv.org/abs/2005.03192">arXiv:2005.03192</A>.},
  length        = {42 pages},
}

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)