Time and space bounds for reversible simulation
- 24 August 2001
- journal article
- Published by IOP Publishing in Journal of Physics A: General Physics
- Vol. 34 (35), 6821-6830
- https://doi.org/10.1088/0305-4470/34/35/308
Abstract
We prove a general upper bound on the trade-off between time and space that suffices for the reversible simulation of irreversible computation. Previously, only simulations using exponential time or quadratic space were known. The trade-off shows for the first time that we can simultaneously achieve subexponential time and subquadratic space. The boundary values are the exponential time with hardly any extra space required by the Lange–McKenzie–Tapp method and the (log 3)th power time with square space required by the Bennett method. We also give the first general lower bound on the extra storage space required by general reversible simulation. This lower bound is optimal in that it is achieved by some reversible simulations.Keywords
Other Versions
This publication has 11 references indexed in Scilit:
- Reversible Space Equals Deterministic SpaceJournal of Computer and System Sciences, 2000
- Reversible simulation of irreversible computationPhysica D: Nonlinear Phenomena, 1998
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- A Note on Bennett’s Time-Space Tradeoff for Reversible ComputationSIAM Journal on Computing, 1990
- Time/Space Trade-Offs for Reversible ComputationSIAM Journal on Computing, 1989
- Miniaturization of electronics and its limitsIBM Journal of Research and Development, 1988
- The thermodynamics of computation—a reviewInternational Journal of Theoretical Physics, 1982
- Conservative logicInternational Journal of Theoretical Physics, 1982
- Logical Reversibility of ComputationIBM Journal of Research and Development, 1973
- Irreversibility and Heat Generation in the Computing ProcessIBM Journal of Research and Development, 1961