EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The Complexity of Iterated Reversible Computation

David Eppstein

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →