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.

A foundational result in origami mathematics is Kawasaki and Justin's simple, efficient characterization of flat foldability for unassigned single-vertex crease patterns (where each crease can fold mountain or valley) on flat material. This result was later generalized to cones of material, where the angles glued at the single vertex may not sum to $360^\circ$. Here we generalize these results to when the material forms a complex (instead of a manifold), and thus the angles are glued at the single vertex in the structure of an arbitrary planar graph (instead of a cycle). Like the earlier characterizations, we require all creases to fold mountain or valley, not remain unfolded flat; otherwise, the problem is known to be NP-complete (weakly for flat material and strongly for complexes). Equivalently, we efficiently characterize which combinatorially embedded planar graphs with prescribed edge lengths can fold flat, when all angles must be mountain or valley (not unfolded flat). Our algorithm runs in $O(n \log^3 n)$ time, improving on the previous best algorithm of $O(n^2 \log n)$.

We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any one of three standard conjectures, we describe a problem that has a data structure where operations run in O(T(n,m)) time per operation, but any partially retroactive version of that data structure requires T(n,m)⋅m^{1-o(1)} worst-case time per operation, where n is the size of the data structure at any time and m is the number of operations. Any data structure with operations running in O(T(n,m)) time per operation can be converted (via the "rollback method") into a partially retroactive data structure running in O(T(n,m)⋅m) time per operation, so our lower bound is tight up to an m^o(1) factor common in fine-grained complexity.

We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using O(n³) monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.

We begin a general theory for characterizing the computational complexity of motion planning of robot(s) through a graph of "gadgets", where each gadget has its own state defining a set of allowed traversals which in turn modify the gadget’s state. We study two general families of such gadgets within this theory, one which naturally leads to motion planning problems with polynomially bounded solutions, and another which leads to polynomially unbounded (potentially exponential) solutions. We also study a range of competitive game-theoretic scenarios, from one player controlling one robot to teams of players each controlling their own robot and racing to achieve their team’s goal. Under certain restrictions on these gadgets, we fully characterize the complexity of bounded 1-player motion planning (NL vs. NP-complete), unbounded 1-player motion planning (NL vs. PSPACE-complete), and bounded 2-player motion planning (P vs. PSPACE-complete), and we partially characterize the complexity of unbounded 2-player motion planning (P vs. EXPTIME-complete), bounded 2-team motion planning (P vs. NEXPTIME-complete), and unbounded 2-team motion planning (P vs. undecidable). These results can be seen as an alternative to Constraint Logic (which has already proved useful as a basis for hardness reductions), providing a wide variety of agent-based gadgets, any one of which suffices to prove a problem hard.