The Complexity of Iterated Reversible Computation
We study a class of functional problems reducible to computing $f^{(n)}(x)$ for inputs $n$ and $x$, where $f$ is a polynomial-time bijection. As we prove, the definition is robust against variations in the type of reduction used in its definition, and in whether we require $f$ to have a polynomial-t...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
TheoretiCS Foundation e.V.
2023-12-01
|
| Series: | TheoretiCS |
| Subjects: | |
| Online Access: | https://theoretics.episciences.org/9072/pdf |
| _version_ | 1797333151664570368 |
|---|---|
| author | David Eppstein |
| author_facet | David Eppstein |
| author_sort | David Eppstein |
| collection | DOAJ |
| description | We study a class of functional problems reducible to computing $f^{(n)}(x)$
for inputs $n$ and $x$, where $f$ is a polynomial-time bijection. As we prove,
the definition is robust against variations in the type of reduction used in
its definition, and in whether we require $f$ to have a polynomial-time inverse
or to be computible by a reversible logic circuit. These problems are
characterized by the complexity class $\mathsf{FP}^{\mathsf{PSPACE}}$, and
include natural $\mathsf{FP}^{\mathsf{PSPACE}}$-complete problems in circuit
complexity, cellular automata, graph algorithms, and the dynamical systems
described by piecewise-linear transformations. |
| first_indexed | 2024-03-08T07:59:37Z |
| format | Article |
| id | doaj.art-69c9a08dae304c55b075a2f1e176d06a |
| institution | Directory Open Access Journal |
| issn | 2751-4838 |
| language | English |
| last_indexed | 2024-03-08T07:59:37Z |
| publishDate | 2023-12-01 |
| publisher | TheoretiCS Foundation e.V. |
| record_format | Article |
| series | TheoretiCS |
| spelling | doaj.art-69c9a08dae304c55b075a2f1e176d06a2024-02-02T12:32:47ZengTheoretiCS Foundation e.V.TheoretiCS2751-48382023-12-01Volume 210.46298/theoretics.23.109072The Complexity of Iterated Reversible ComputationDavid EppsteinWe study a class of functional problems reducible to computing $f^{(n)}(x)$ for inputs $n$ and $x$, where $f$ is a polynomial-time bijection. As we prove, the definition is robust against variations in the type of reduction used in its definition, and in whether we require $f$ to have a polynomial-time inverse or to be computible by a reversible logic circuit. These problems are characterized by the complexity class $\mathsf{FP}^{\mathsf{PSPACE}}$, and include natural $\mathsf{FP}^{\mathsf{PSPACE}}$-complete problems in circuit complexity, cellular automata, graph algorithms, and the dynamical systems described by piecewise-linear transformations.https://theoretics.episciences.org/9072/pdfcomputer science - computational complexitynonlinear sciences - cellular automata and lattice gases68q10, 68q15, 68q80f.1.1 |
| spellingShingle | David Eppstein The Complexity of Iterated Reversible Computation TheoretiCS computer science - computational complexity nonlinear sciences - cellular automata and lattice gases 68q10, 68q15, 68q80 f.1.1 |
| title | The Complexity of Iterated Reversible Computation |
| title_full | The Complexity of Iterated Reversible Computation |
| title_fullStr | The Complexity of Iterated Reversible Computation |
| title_full_unstemmed | The Complexity of Iterated Reversible Computation |
| title_short | The Complexity of Iterated Reversible Computation |
| title_sort | complexity of iterated reversible computation |
| topic | computer science - computational complexity nonlinear sciences - cellular automata and lattice gases 68q10, 68q15, 68q80 f.1.1 |
| url | https://theoretics.episciences.org/9072/pdf |
| work_keys_str_mv | AT davideppstein thecomplexityofiteratedreversiblecomputation AT davideppstein complexityofiteratedreversiblecomputation |