The Complexity of Iterated Reversible Computation
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-t...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
TheoretiCS Foundation e.V.
2023-12-01
|
| Series: | TheoretiCS |
| Subjects: | |
| Online Access: | https://theoretics.episciences.org/9072/pdf |