PSPACE-Completeness of Reversible Deterministic Systems.
Saved in:
| Title: | PSPACE-Completeness of Reversible Deterministic Systems. |
|---|---|
| Authors: | Demaine, Erik D.1 (AUTHOR) edemaine@mit.edu, Hearn, Robert A.1 (AUTHOR) bob@hearn.to, Hendrickson, Dylan1 (AUTHOR) dylanhen@mit.edu, Lynch, Jayson1 (AUTHOR) jaysonl@mit.edu |
| Source: | International Journal of Foundations of Computer Science. Nov2025, Vol. 36 Issue 7, p1041-1062. 22p. |
| Subjects: | Reversible computing, Computational complexity, Deterministic algorithms, Planning techniques, Constraint programming |
| 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. [ABSTRACT FROM AUTHOR] |
| Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
Be the first to leave a comment!
