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

DOI10.1016/j.tcs.2023.113945arXiv2005.03192OpenAlexW4379141356MaRDI QIDQ6165551

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

Publication date: 1 August 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

switching systemsPSPACENPgames and puzzlesARRIVAL

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Did the train reach its destination: the complexity of finding a witness
• Trainyard is NP-hard
• Unique end of potential line
• Relationships between nondeterministic and deterministic tape complexities
• 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
• The complexity of graph connectivity
• Unnamed Item
• Unnamed Item
• 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