Paper by Erik D. Demaine
- Erik D. Demaine, Robert A. Hearn, Dylan Hendrickson, and Jayson Lynch, “PSPACE-Completeness of Reversible Deterministic Systems”, in Proceedings of the 9th Conference on Machines, Computations and Universality (MCU 2022), Debrecen, Hungary, August 31–September 2, 2022, pages 91–108.
We prove PSPACE-completeness of several reversible, fully deterministic
systems. At the core, we develop a framework for such proofs (building on a
result of Tsukiji and Hagiwara and a framework for motion planning through
gadgets), showing that any system that can implement three basic gadgets is
PSPACE-complete. We then apply this framework to four different systems,
showing its versatility. First, we prove that Deterministic Constraint Logic
is PSPACE-complete, fixing an error in a previous argument from 2008. Second,
we give a new PSPACE-hardness proof for the reversible ‘billiard
ball’ model of Fredkin and Toffoli from 40 years ago, newly establishing
hardness when only two balls move at once. Third, we prove
PSPACE-completeness of zero-player motion planning with any reversible
deterministic interacting k-tunnel gadget and a ‘rotate
clockwise’ gadget (a zero-player analog of branching hallways). Fourth,
we give simpler proofs that zero-player motion planning is PSPACE-complete
with just a single gadget, the 3-spinner. These results should in turn make
it even easier to prove PSPACE-hardness of other reversible deterministic
- The paper is available in PDF (566k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 19, 2022 by