Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2112.11607 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911775786532864 |
|---|---|
| author | Eppstein, David |
| author_facet | Eppstein, David |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2112_11607 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Complexity of Iterated Reversible Computation Eppstein, David Computational Complexity Cellular Automata and Lattice Gases 68Q10, 68Q15, 68Q80 F.1.1 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. |
| title | The Complexity of Iterated Reversible Computation |
| topic | Computational Complexity Cellular Automata and Lattice Gases 68Q10, 68Q15, 68Q80 F.1.1 |
| url | https://arxiv.org/abs/2112.11607 |