Paper by Erik D. Demaine
- Reference:
- Hayashi Ani, Erik D. Demaine, Jenny Diomidova, Della Hendrickson, and Jayson Lynch, “Traversability, Reconfiguration, and Reachability in the Gadget Framework”, Algorithmica, volume 85, number 11, 2023, pages 3453–3486.
- Abstract:
-
Consider an agent traversing a graph of “gadgets”, where each
gadget has local state that changes with each traversal by the agent according
to specified rules. Prior work has studied the computational complexity of
deciding whether the agent can reach a specified location, a problem we call
reachability. This paper introduces new goals for the agent, aiming to
characterize when the computational complexity of these problems is the same
or differs from that of reachability. First we characterize the complexity of
universal traversal—where the goal is to traverse every gadget at
least once—for DAG gadgets (partially), one-state gadgets, and
reversible deterministic gadgets. Then we study the complexity of
reconfiguration—where the goal is to bring the system of gadgets
to a specified state. We prove many cases PSPACE-complete, and show in some
cases that reconfiguration is strictly harder than reachability, while in
other cases, reachability is strictly harder than reconfiguration.
- Comments:
- This paper is also available as arXiv:2204.00600 and from SpringerLink.
- Availability:
- The paper is available in PDF (699k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- GadgetsVictory_WALCOM2022 (Traversability, Reconfiguration, and Reachability in the Gadget Framework)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.