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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The time evolution of the wave-function in the Standard Model is deterministic even if the observation of macroscopic phenomena is probabilistic.
- 2.
- 3.
Tsukiji and Hagiwara call these ‘OUT\(_{i,\text {FALSE}}\)’, ‘OUT\(_{i,\text {TRUE}}\)’, ‘IN\(_i\)’, ‘I\(_{x_i}\)’, ‘O\(_{x_i}\)’, ‘IN\(_{i+1}\)’, ‘OUT\(_{i+1,\text {TRUE}}\)’, and ‘OUT\(_{i+1,\text {FALSE}}\)’, respectively.
- 4.
Alternatively, avoid this crossing by adjusting the Reversible Fan-in connecting x and y.
- 5.
In grayscale, blue edges are darker than red edges. Figures also draw blue edges thicker than red edges.
References
Ani, J., Demaine, E.D., Hendrickson, D.H., Lynch, J.: Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets. In: Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022) (2022). arXiv:2005.03192
Demaine, E.D., Grosof, I., Lynch, J., Rudoy, M.: Computational complexity of motion planning of a robot through simple gadgets. In: Proceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), pp. 18:1–18:21 (2018)
Demaine, E.D., Hearn, R.A.: Constraint logic: a uniform framework for modeling computation as games. In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, pp. 149–162, June 2008
Demaine, E.D., Hendrickson, D.H., Lynch, J.: Toward a general complexity theory of motion planning: characterizing which gadgets make games hard. In: Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), pp. 62:1–62:42 (2020)
Demaine, E.D., Lynch, J., Mirano, G.J., Tyagi, N.: Energy-efficient algorithms. In: Proceedings of the 7th Annual ACM Conference on Innovations in Theoretical Computer Science (ITCS 2016), Cambridge, Massachusetts, pp. 321–332, 14–16 January 2016
Frank, M.P.: Fundamental physics of reversible computing-an introduction. Technical report, Sandia National Lab. (SNL-NM), Albuquerque, NM, USA (2020)
Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theor. Phys. 21(3), 219–253 (1982)
Hearn, R.A., Demaine, E.D.: Games, Puzzles, and Computation. CRC Press, Boca Raton (2009)
Hendrickson, D.: Gadgets and Uizmos: a formal model of simulation in the gadget framework for motion planning. Ph.D. thesis, Massachusetts Institute of Technology (2021)
Özdemir, Ş.K., Rotter, S., Nori, F., Yang, L.: Parity-time symmetry and exceptional points in photonics. Nat. Mater. 18(8), 783–798 (2019). https://doi.org/10.1038/s41563-019-0304-9
Tsukiji, T., Hagiwara, T.: Recognizing the repeatable configurations of time-reversible generalized Langton’s ant is PSPACE-hard. Algorithms 4(1), 1–15 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Demaine, E.D., Hearn, R.A., Hendrickson, D., Lynch, J. (2022). PSPACE-Completeness of Reversible Deterministic Systems. In: Durand-Lose, J., Vaszil, G. (eds) Machines, Computations, and Universality. MCU 2022. Lecture Notes in Computer Science, vol 13419. Springer, Cham. https://doi.org/10.1007/978-3-031-13502-6_7
Download citation
DOI: https://doi.org/10.1007/978-3-031-13502-6_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-13501-9
Online ISBN: 978-3-031-13502-6
eBook Packages: Computer ScienceComputer Science (R0)