PSPACE-completeness of reversible deterministic systems

DOI10.1142/S0129054123470032MaRDI QIDQ6902485zbMATH OpenFDO

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

Publication date 11 November 2025

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054123470032

zbMATH Keywords

computational complexityconstraint logicPSpacereversible computing

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of game theory (91A80)

Cites work

• Computational complexity of motion planning of a robot through simple gadgets
• Conservative logic
• Energy-efficient algorithms
• Games, puzzles, and computation
• scientific article; zbMATH DE number 7650410 (Why is no real title available?)
• 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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902485)