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.

BibTeX

@InProceedings{DCL_MCU2022,
  AUTHOR        = {Erik D. Demaine and Robert A. Hearn and Della Hendrickson and Jayson Lynch},
  authororig    = {Erik D. Demaine and Robert A. Hearn and Dylan Hendrickson and Jayson Lynch},
  TITLE         = {{PSPACE}-Completeness of Reversible Deterministic Systems},
  BOOKTITLE     = {Proceedings of the 9th Conference on Machines, Computations and Universality (MCU 2022)},
  bookurl       = {https://konferencia.unideb.hu/en/mcu-2022},
  ADDRESS       = {Debrecen, Hungary},
  MONTH         = {August 31--September 2},
  YEAR          = 2022,
  PAGES         = {91--108},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-031-13502-6_7},
  dblp          = {https://dblp.org/rec/conf/mcu/DemaineHHL22},
  comments      = {The full paper is available as <A HREF="https://arxiv.org/abs/2207.07229">arXiv:2207.07229</A>, and from <A HREF="https://doi.org/10.1007/978-3-031-13502-6_7">SpringerLink</A>.},
}

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, and from SpringerLink.

Availability:

The paper is available in PDF (566k).

See information on file formats.

[Google Scholar search]