Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Robert A. Hearn, Della 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.

Abstract:

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 systems.

Comments:

The full paper is available as arXiv:2207.07229.

Availability:

The paper is available in PDF (566k).

See information on file formats.

[Google Scholar search]