Function permanent(NxN) has N2 inputs and ]log(N!)[ outputs. It computes permanent of a 0-1 matrix. L. Valiant showed that such permanent is #P-Complete. Thus, this function is among those we believe are the most complex---there is strong evidence that no polynomial time classical algorithm exists to compute permanent.
Function permanent(NxN) may be embedded into a reversible specification in many ways. A trivial approach that does not guarantee minimal garbage is to introduce ]log(N!)[ input constants and EXOR output value with those bits. This results in a reversible specification with N2+]log(N!)[ inputs/outputs, permanentNxN.
A number of single output Boolean functions may be generated each of which is polynomially reducible to computing permanent(NxN). Each of such functions is as hard (up to a small polynomial factor) as computing the permanent itself. For example, an N2+]log(N!)[-input single output function may be defined to return zero if permanent of the 0-1 matrix coded on the first N2 bits is less than or equal to the number coded by the remaining ]log(N!)[ inputs; otherwise, return one. A Boolean function may have N2+]loglog(N!)[ inputs and one output, and return k-th bit of the permanent, where matrix is coded in the first N2 inputs, and the remaining ]loglog(N!)[ bits are used to code value of the bit being extracted. It is likely that P2 mod 3 where P is permanent of an NxN 0-1 matrix (it is easy to see that the relevant number is always zero or one, i.e., it takes a Boolean value), a function with N2 inputs and one output, is as hard as computing the permanent itself (P mod 3 is #P complete).
Thanks to Dima Gavinsky for relevant discussions and suggestions.