The Complexity of Iterated Reversible Computation
The Complexity of Iterated Reversible Computation
复制标题
迭代可逆计算的复杂性
DOI：
10.46298/theoretics.23.10
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
D. Eppstein
中科院分区：
文献类型：
--
作者：
D. Eppstein
我们研究一类可简化为计算 $f^{(n)}(x)$ 的功能问题
对于输入 $n$ 和 $x$，其中 $f$ 是多项式时间双射。正如我们证明的那样，
该定义对于所使用的归约类型的变化是稳健的
它的定义，以及我们是否要求 $f$ 具有多项式时间逆
或可通过可逆逻辑电路进行计算。这些问题是
以复杂度类别 $\mathsf{FP}^{\mathsf{PSPACE}}$ 为特征，并且
包括电路中自然的$\mathsf{FP}^{\mathsf{PSPACE}}$完全问题
复杂性、元胞自动机、图算法和动力系统
通过分段线性变换来描述。
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.
八角镜迷宫中的倒影
DOI：
--
发表时间：
2022
期刊：
34th Canadian Conference on Computational Geometry
影响因子：
--
作者：
Eppstein, David
通讯作者：
Eppstein, David