View in EDS

PSPACE-Completeness of Reversible Deterministic Systems.

Saved in:
Bibliographic Details
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
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 189134532
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: PSPACE-Completeness of Reversible Deterministic Systems.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Demaine%2C+Erik+D%2E%22">Demaine, Erik D.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> edemaine@mit.edu</i><br /><searchLink fieldCode="AR" term="%22Hearn%2C+Robert+A%2E%22">Hearn, Robert A.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> bob@hearn.to</i><br /><searchLink fieldCode="AR" term="%22Hendrickson%2C+Dylan%22">Hendrickson, Dylan</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> dylanhen@mit.edu</i><br /><searchLink fieldCode="AR" term="%22Lynch%2C+Jayson%22">Lynch, Jayson</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> jaysonl@mit.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Foundations+of+Computer+Science%22">International Journal of Foundations of Computer Science</searchLink>. Nov2025, Vol. 36 Issue 7, p1041-1062. 22p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Reversible+computing%22">Reversible computing</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Deterministic+algorithms%22">Deterministic algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Planning+techniques%22">Planning techniques</searchLink><br /><searchLink fieldCode="DE" term="%22Constraint+programming%22">Constraint programming</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>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.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189134532
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1142/S0129054123470032
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 22
        StartPage: 1041
    Subjects:
      – SubjectFull: Reversible computing
        Type: general
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Deterministic algorithms
        Type: general
      – SubjectFull: Planning techniques
        Type: general
      – SubjectFull: Constraint programming
        Type: general
    Titles:
      – TitleFull: PSPACE-Completeness of Reversible Deterministic Systems.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Demaine, Erik D.
      – PersonEntity:
          Name:
            NameFull: Hearn, Robert A.
      – PersonEntity:
          Name:
            NameFull: Hendrickson, Dylan
      – PersonEntity:
          Name:
            NameFull: Lynch, Jayson
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 11
              Text: Nov2025
              Type: published
              Y: 2025
          Identifiers:
            – Type: issn-print
              Value: 01290541
          Numbering:
            – Type: volume
              Value: 36
            – Type: issue
              Value: 7
          Titles:
            – TitleFull: International Journal of Foundations of Computer Science
              Type: main
ResultId 1