6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

Prof. Erik Demaine TAs: Josh Brunner, Lily Chung, Jenny Diomidova

[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Lecture 11 Video [previous] [next]

[+] Motion-Planning Gadgets. Gadgets, states, locations, transitions, traversals, tunnels, buttons; system, connection graph, reachability, simulation. Door, self-closing door, symmetric self-closing door, universality, planarity. Deterministic reversible gadgets, hardness characterization, 2-state 2-tunnel gadgets. Checkable gadgets, Sokoban, Push-1F. I/O gadgets, 0-player, ARRIVAL. DAG vs. LDAG gadgets.

Gadgets gadgets gadgets! This lecture describes a growing general theory of "gadgets" in the context of "motion planning": an agent (e.g., Mario) traversing an environment with local state. We'll define a very general model of such gadgets, where each gadget consists of states, locations, and transitions between pairs of states and locations, and systems/networks of these gadgets connected in a graph structure. Then we'll describe some of the key results in this ongoing theory:

Door framework: three gadgets that can each universally simulate all gadgets, even with a planar network (no crossings).
Deterministic reversible gadgets: a complete characterization of which such gadgets are PSPACE-complete, with one gadget (Locking 2-Toggle) serving as a "basis" that every such gadget can simulate.
Checkable gadgets framework: Lets you effectively ignore "broken" states in a gadget, as long as they are detectable (disable a particular traversal) and broken states stay broken. As an application, we'll see a solution to the long-standing open problem: Push-1F is PSPACE-complete.
I/O gadgets and 0-player motion planning (fully deterministic system, still PSPACE-complete).
DAG gadgets, and their relation to the door opening/closing gadgets we saw in Lecture 6.