I asked this in [cstheory.SE](https://cstheory.stackexchange.com/questions/42204/reversible-polynomial-circuit-iff-polynomial-reversible-circuit) a week ago. Since there are no answers or comments, and since this is perhaps more about permutations than computation, I hope it is ok to cross-post here as well.


My question is about efficiently computable bijective functions. Informally I'm interested in:



> 
> If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective gates?
> 
> 
> 


I have checked the list of relevant questions and didn't spot this one (here or in cstheory). My precise setting may or may not be orthodox so I include my definitions. I believe the question is research level, but I'm happy to be proven wrong.


Let $B = \{0,1\}$. Let's define a **gate** as an element of $\mathrm{Alt}(B^n)$ for some finite $n$. For finite $N$ define $G\_N = \bigcup\_{n \leq N} \mathrm{Alt}(B^n)$, and define $G\_\infty = \bigcup\_n \mathrm{Alt}(B^n)$. For two gates $\pi\_1 \in \mathrm{Alt}(B^m), \pi\_2 \in \mathrm{Alt}(B^n)$ write $\pi = \pi\_1 | \pi\_2$ for the permutation $B^{m+n}$ defined by $\pi(u \cdot v) = \pi\_1(u) \cdot \pi\_2(v)$ for $u \in B^m, v \in B^n$, where $\cdot$ is concatenation of words. For a set of gates $G$ write $\lceil G \rceil$ for the smallest subset of $\bigcup\_n \mathrm{Alt}(B^n)$ containing the identity maps and closed under well-defined function compositions $(\pi\_1, \pi\_2) \mapsto \pi\_1 \circ \pi\_2$, and under the operation $|$.


It's known that $\lceil G\_N \rceil = G\_\infty$ for all $N \geq 4$, let's fix $N = 4$ for concreteness. Concretely this means that any $\pi \in \mathrm{Alt}(B^n)$ for any $n \geq N$ can be written as
$\pi = \phi\_k \circ \cdots \circ \phi\_2 \circ \phi\_1$
for some $k$, where for each $\phi\_i$ there exists $\ell\_i$ and $\pi\_i \in \mathrm{Alt}(B^4)$ such that $\phi\_i(u \cdot v \cdot w) = u \cdot \pi\_i(v) \cdot w$ for all $|u| = \ell\_i, |v| = 4$.


For $\pi \in \mathrm{Alt}(B^n)$ an even permutation. If $n \geq 4$, define its **reversible gate complexity** as the minimal $k$ such that $\pi$ can be written as a composition like the one above. If $n < 4$, define the gate complexity of $\pi$ to be $1$. (One may wish to allow conjugation of gates by the permutations by $uabv \mapsto ubav$. This changes gate complexity only by a linear factor, so for the present purpose it does not matter.)



> 
> Suppose that both $\pi \in \mathrm{Alt}(B^n)$ and its inverse are efficiently computable in some sense, e.g. polynomial time, NC$^d$, logspace... Is the reversible gate complexity of $\pi$ then necessarily polynomial in $n$?
> 
> 
> 


Some observations:


* The proof of Barrington's theorem shows that for a fixed $m \geq 3$, if $\pi$ is of the special form $\pi(u \cdot w) = \psi(u, w) \cdot w$ for some function $\psi : B^m \times B^n \to B^m$, such that the permutations in the $w$-fibers $\{u \cdot w \;|\; u \in B^m\}$ are even for each $w \in B^n$, then the reversible gate complexity of $\pi$ is polynomial in $n$ whenever $\pi$ is in NC$^1$. Namely if there is an NC$^1$ circuit for $\psi$, then there is an NC$^1$ circuit (larger by a constant factor) with $2^m!/2$ special output nodes that record whether a particular permutation was performed in the first $m$ coordinates. We can then show (as in Barrington's theorem's proof) that for each node in this network, every even permutation conditioned on any value of that node, has a polynomial size circuit complexity in $n$. Now combine the ones corresponding to the new special nodes to get a polynomial gate complexity for $\pi$.
* Bennett's trick shows (among other things) that if $\pi \in \mathrm{Alt}(B^n)$ and $\pi^{-1}$ have gate complexity $m$ (computable by an acyclic network of $m$ two-input classical gates), then there is permutation $\pi' \in \mathrm{Alt}(B^{n+m})$ with reversible gate complexity polynomial in $n + m$ such that $\pi'(u \cdot 0^{n+m}) = (\pi(u) \cdot 0^{n+m})$ for all $u \in B^n$. Namely, let $f$ compute the values of the network in the last $m$ bits, w.r.t. some topological sorting of the network (assuming they are $0$; otherwise we do not care). Let $g$ be the map that sums the $n$ answer bits to the $n$ bits after $u$. Let $h$ exchange the first and second word of length $n$. Then $h \circ f^{-1} \circ g \circ f$ proves the claim.
* One-way bijections in cryptography are permutations of $B^n$, which have the property that they can be computed in polynomial time, but cannot be inverted in polynomial time. (Their defining property is much stronger, but I don't think it's relevant here.) I don't know if this particular definition directly has anything to do with the present problem, as we're dealing with a non-uniform computation model.



Reversible polynomial circuit = polynomial reversible circuit?
There is an easy trick that one can use to encode any function into a bijective function.


Suppose $f:2^{m}\rightarrow 2^{n}$ is an arbitrary function.


Define $L\_{f}:2^{m}\times 2^{n}\rightarrow 2^{m}\times 2^{n}$ by letting
$L\_{f}(x,y)=(x,y\oplus f(x))$.


For a more optimized argument, let us define the reversible gate complexity with free swap as the reversible gate complexity where the gate where we simply swap two bits is free. Suppose that $L\_{f}$ has reversible gate complexity with free swaps $k$. Then the function $f$ can be computed by a combinatorial circuit of width $O(m+n)$ consisting of $O(k)$ gates. Thus, $L\_{f}$ has reasonable reversible circuit complexity only when $f$ can be computed with very little space. I doubt that the converse holds.


I should mention that reversible space $O(S(n))$ Turing machines can simulate conventional space $S(n)$ Turing machines at the expense that the reversible Turing machines may take an exponential amount of time, so some space saving reversible computation is possible.


<https://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2013W/LMT_ReversibleSpace.pdf>


