Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets

DOI10.1007/978-3-030-96731-4_16OpenAlexW3023230561MaRDI QIDQ2154096

Dylan Hendrickson, Jayson Lynch, Joshua Ani, Erik D. Demaine

Publication date: 13 July 2022

Full work available at URL: https://arxiv.org/abs/2005.03192

zbMATH Keywords

motion planninggadgetshardness of games

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (2)

Traversability, reconfiguration, and reachability in the gadget framework ⋮ PSPACE-completeness of reversible deterministic systems

Cites Work

• Did the train reach its destination: the complexity of finding a witness
• Unique end of potential line
• Tracks from hell - When finding a proof may be easier than checking it
• ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP
• ARRIVAL: Next Stop in CLS
• Reachability Switching Games
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets