PSPACE-completeness of reversible deterministic systems

DOI10.1007/978-3-031-13502-6_7OpenAlexW4290017147MaRDI QIDQ2104136

Erik D. Demaine, Jayson Lynch, Robert A. Hearn, Dylan Hendrickson

Publication date: 9 December 2022

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Traversability, reconfiguration, and reachability in the gadget framework

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Conservative logic
• Recognizing the repeatable configurations of time-reversible generalized Langton's ant is PSPACE-hard
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• Energy-Efficient Algorithms

This page was built for publication: PSPACE-completeness of reversible deterministic systems