  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.
