The Complexity of Iterated Reversible Computation
TheoretiCS · 2023
DOI: 10.46298/theoretics.23.10 ↗Kurz gefasst
Fachartikel in der Zeitschrift TheoretiCS, 2023. Verfasst von David Eppstein. Die Arbeit wurde bisher 1-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Eppstein, D. (2023). The Complexity of Iterated Reversible Computation. TheoretiCS. https://doi.org/10.46298/theoretics.23.10
Vancouver
Eppstein D. The Complexity of Iterated Reversible Computation. TheoretiCS. 2023. doi:10.46298/theoretics.23.10
BibTeX
@article{Eppstein2023,
author = {Eppstein, David},
title = {The Complexity of Iterated Reversible Computation},
journal = {TheoretiCS},
year = {2023},
doi = {10.46298/theoretics.23.10}
}
EUVIMED