Name
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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/978-3-031-13502-6_7 | Machines, Computations, and Universality |
DocType | Volume | ISSN |
Conference | 13419 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik D. Demaine | 1 | 4624 | 388.59 |
| Robert A. Hearn | 2 | 169 | 20.52 |
| Dylan Hendrickson | 3 | 0 | 0.34 |
| Jayson Lynch | 4 | 0 | 0.34 |