Enumeration of reversible functions and its application to circuit complexity

We review combinational results to enumerate and classify reversible functions and investigate the application to circuit complexity. In particularly, we consider the effect of negating and permuting input and output variables and the effect of applying linear and affine transformations to inputs and outputs. We apply the results to reversible circuits and prove that minimum circuit realizations of functions in the same equivalence class differ at most in a linear number of gates in pres- ence of negation and permutation and at most in a quadratic number of gates in presence of linear and affine transformations.