A Note on Bennett’s Time-Space Tradeoff for Reversible Computation

Robert Y. Levine, Alan T. Sherman · 1990 · SIAM J. Comput. 19(1)

| 编号 QRC003 | 主题 可逆计算与编译 | 链接 DOI 10.1137/0219046 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

Given any irreversible program with running time T and space complexity S, and given any \varepsilon > 0, Bennett shows how to construct an equivalent reversible program with running time $O(T^{1+\epsilon })$ and space complexity $O(S\ln T)$. Although these loose upper bounds are formally correct, they are misleading due to a hidden constant factor in the space bound. It is shown that this constant factor is approximately $\epsilon 2^{1/\epsilon }$, which diverges exponentially as $\epsilon$ approaches 0. Bennett’s analysis is simplified using recurrence equations and it is proven that the reversible program actually runs in time $\Theta (T^{1+\epsilon }/S^{\epsilon })$ and space $\Theta (S(1+\ln (T/S)))$. Bennett claims that for any \varepsilon > 0, the reversible program can be made to run in time $O(T)$ and space $O(S{T}^{\epsilon })$. This claim is corrected and tightened as follows: whenever $T\geqq 2S$ and for any $\epsilon \geqq 1/(0.58\lg (T/S))$, the reversible program can be made to run in time $\Theta (T)$ and space $\Omega (S(T/S{)}^{\epsilon /2})\cap O(S(T/S{)}^{\epsilon })$. For S\leqq T < 2S, Bennett’s 1973 simulation yields an equivalent reversible program that runs in time $\Theta (T)$ and space $\Theta (S)$.

本站词条在引用该文献时，会以 wikilink（sources/QRC003）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。