Abstract of Paper

On the Computational Complexity of Conservative Computing
by Giancarlo Mauri and Alberto Leporati


In a seminal paper published in 1982, Fredkin and Toffoli have introduced
\emph{conservative logic}, a mathematical model that allows one to describe
computations which reflect some properties of microdynamical laws of
Physics, such as reversibility and conservation of the internal energy of the
physical system used to perform the computations. In particular, conservativeness is
defined as a mathematical property whose goal is to model the conservation
of the energy associated to the data which are manipulated during the
computation of a logic gate.

Extending such notion to generic gates whose input and output lines may
assume a finite number $d$ of truth values, we define \emph{conservative
computations} and we show that they naturally induce a new NP--complete 
decision problem and an associated NP--hard optimization problem.
Moreover, we briefly describe the results of five computer experiments
performed to study the behavior of some polynomial time heuristics which
give approximate solutions to such optimization problem.

Since the computational primitive underlying conservative logic is the
Fredkin gate, we advocate the study of the computational power of \emph{Fredkin
circuits}, that is circuits composed by Fredkin gates.
Accordingly, we give some first basic results about the classes of Boolean
functions which can be computed through polynomial--size constant--depth
Fredkin circuits.