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.

Download Video: 360p, 720p

Handwritten notes, page 1/11[previous page][next page][PDF]

Handwritten notes, page 1/11[previous page][next page][PDF]

Slides, page 1/67[previous page][next page][PDF]

https://erikdemaine.org/papers/Mario_FUN2016/

Slides, page 1/67[previous page][next page][PDF]