A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
Robert Y. Levine, Alan T. Sherman · SIAM Journal on Computing · 1990
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+\varepsilon })$ 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 $\varepsilon 2^{1 / \varepsilon}$, which diverges exponentially as $\varepsilon$ 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 + \varepsilon}} / {S^{\varepsilon}}})$ 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(ST^{\varepsilon })$. This claim is corrected and tightened as follows: whenever $T \geqq 2S$ and for any $\varepsilon \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)^{\varepsilon/2})\cap O(S(T/S)^\varepsilon )$. For $S\leqq T < 2S$, Bennett’s 1973 simulation yields an equivalent reversible program that runs in time $\Theta (T)$ and space $\Theta (S)$.