3 papers
cs.CC2024
Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
Hayashi Ani, Lily Chung, Erik D. Demaine +3
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (introduced in 1999). The proof also extends to Push-$k…
cs.LO2023
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines
Hayashi Ani, Michael Coulombe, Erik D. Demaine +4
We extend the motion-planning-through-gadgets framework to several new scenarios involving various numbers of robots/agents, and analyze the complexity of the resulting motion-plan…
cs.CC2023
This Game Is Not Going To Analyze Itself
Aviv Adler, Hayashi Ani, Lily Chung +5
We analyze the puzzle video game This Game Is Not Going To Load Itself, where the player routes data packets of three different colors from given sources to given sinks of the corr…