Separations of reversible and irreversible space-time complexity classes
Abstract: Reversible computing can reduce the energy
dissipation of computation, which can improve cost-efficiency in some
contexts. But the practical applicability of this method depends
sensitively on the space and time overhead required by reversible
algorithms. Time and space complexity classes for reversible machines
match conventional ones, but we conjecture that the joint
space-time complexity classes are different, and that a
particular reduction by Bennett minimizes the space-time
product complexity of general reversible computations. We provide
an oracle-relativized proof of the separation, and of a lower bound on
space for linear-time reversible simulations. A non-oracle proof
applies when a read-only input is omitted from the space accounting.
Both constructions model one-way function iteration, conjectured to be
a problem for which Bennett's algorithm is optimal.
Most recent versions first:
Revised and expanded version submitted to Information and Computation
(39 pp.):
-
LaTeX (minus figs, up to date)
-
DVI (minus figs, up to date)
-
Postscript (includes figs, may be
slightly out of date)
-
PDF (includes figs, may be slightly
out of date)
Course manuscript version: see chapter 3 under this
page.
Ph.D. Thesis version: see chapter 3 under this
page.
Extended abstract to be submitted to CCC-98 (10 pp, out of date):
A longer version will be prepared for submission to the journal Information
and Computation.
Original working draft memo (~28 pp, out of date):
This paper is part of the M series of working memos produced by the MIT
Reversible Computing Project.
Michael Frank 4/3/97