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

Given any irreversible program with running time T and space complexity S, and given any ε > 0, Bennett shows how to construct an equivalent reversible program with running time O(T1+ε) 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 ε 21 / ε, which diverges exponentially as ε approaches 0. Bennett’s analysis is simplified using recurrence equations and it is proven that the reversible program actually runs in time Θ (T1 + ε / Sε) and space Θ (S(1+ln (T / S))). Bennett claims that for any ε > 0, the reversible program can be made to run in time $O(T)$ and space O(STε). This claim is corrected and tightened as follows: whenever T 2S and for any ε 1 / (0.58 (T / S)), the reversible program can be made to run in time Θ (T) and space Ω (S(T/S)ε/2)∩ O(S(T/S)^ε ). For S T < 2S, Bennett’s 1973 simulation yields an equivalent reversible program that runs in time Θ (T) and space Θ (S).