The Complexity of Iterated Reversible Computation

We define a complexity class $\mathsf{IB}$ as the 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. We relate $\mathsf{IB}$ to other standard complexity classes, and demonstrate its applicability by finding natural $\mathsf{IB}$-complete problems in circuit complexity, cellular automata, graph algorithms, and the dynamical systems described by piecewise-linear transformations.Comment: 33 pages, 7 figures. This version adds a polynomial-time solution to the iterated integer interval exchange problem, listed as open in the previous versio