Traversability, Reconfiguration, and Reachability in the Gadget Framework
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 p...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2023
|
| Online Access: | https://hdl.handle.net/1721.1/151069 |
| _version_ | 1826203279386738688 |
|---|---|
| author | Ani, Joshua Demaine, Erik D. Diomidov, Yevhenii Hendrickson, Dylan Lynch, Jayson |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Ani, Joshua Demaine, Erik D. Diomidov, Yevhenii Hendrickson, Dylan Lynch, Jayson |
| author_sort | Ani, Joshua |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T12:34:24Z |
| format | Article |
| id | mit-1721.1/151069 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:34:24Z |
| publishDate | 2023 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1510692024-01-12T20:30:09Z Traversability, Reconfiguration, and Reachability in the Gadget Framework Ani, Joshua Demaine, Erik D. Diomidov, Yevhenii Hendrickson, Dylan Lynch, Jayson Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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. 2023-07-10T18:48:07Z 2023-07-10T18:48:07Z 2023-07-05 2023-07-09T03:17:25Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/151069 Ani, Joshua, Demaine, Erik D., Diomidov, Yevhenii, Hendrickson, Dylan and Lynch, Jayson. 2023. "Traversability, Reconfiguration, and Reachability in the Gadget Framework." PUBLISHER_CC en https://doi.org/10.1007/s00453-023-01140-0 Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer US Springer US |
| spellingShingle | Ani, Joshua Demaine, Erik D. Diomidov, Yevhenii Hendrickson, Dylan Lynch, Jayson Traversability, Reconfiguration, and Reachability in the Gadget Framework |
| title | Traversability, Reconfiguration, and Reachability in the Gadget Framework |
| title_full | Traversability, Reconfiguration, and Reachability in the Gadget Framework |
| title_fullStr | Traversability, Reconfiguration, and Reachability in the Gadget Framework |
| title_full_unstemmed | Traversability, Reconfiguration, and Reachability in the Gadget Framework |
| title_short | Traversability, Reconfiguration, and Reachability in the Gadget Framework |
| title_sort | traversability reconfiguration and reachability in the gadget framework |
| url | https://hdl.handle.net/1721.1/151069 |
| work_keys_str_mv | AT anijoshua traversabilityreconfigurationandreachabilityinthegadgetframework AT demaineerikd traversabilityreconfigurationandreachabilityinthegadgetframework AT diomidovyevhenii traversabilityreconfigurationandreachabilityinthegadgetframework AT hendricksondylan traversabilityreconfigurationandreachabilityinthegadgetframework AT lynchjayson traversabilityreconfigurationandreachabilityinthegadgetframework |