**Reversible Logic Synthesis Benchmarks Page**

**you are in... Main\permanent**
Function permanent(NxN) has *N*^{2}
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 *N*^{2}+*]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 *N*^{2}+*]log(N!)[*-input
single output function may be defined to return zero if permanent of the 0-1
matrix coded on the first *N*^{2} bits is less than or equal to the
number coded by the remaining *]log(N!)[* inputs; otherwise, return one. A
Boolean function may have *N*^{2}+*]loglog(N!)[* inputs and
one output, and return k-th bit of the permanent, where matrix is coded in the
first *N*^{2} inputs, and the remaining *]loglog(N!)[* bits
are used to code value of the bit being extracted. It is likely that *P*^{2}
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 *N*^{2} 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.