David Eppstein - The Complexity of Iterated Reversible Computation

theoretics:9072 - TheoretiCS, December 26, 2023, Volume 2 - https://doi.org/10.46298/theoretics.23.10
The Complexity of Iterated Reversible ComputationArticle

Authors: David Eppstein

    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.


    Volume: Volume 2
    Published on: December 26, 2023
    Accepted on: November 27, 2023
    Submitted on: February 10, 2022
    Keywords: Computer Science - Computational Complexity,Nonlinear Sciences - Cellular Automata and Lattice Gases,68Q10, 68Q15, 68Q80,F.1.1

    Consultation statistics

    This page has been seen 264 times.
    This article's PDF has been downloaded 131 times.