I asked this in cstheory.SE 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.

  • $\begingroup$ What is $\mathrm{Alt}$? Even permutations? (Why just even permutations?) $\endgroup$ – François G. Dorais Jan 21 at 12:33
  • 2
    $\begingroup$ Yes the even ones, and because $G_\infty$ is not finitely generated in the above sense if we use Sym (and the set of bits is even), since a permutation applied to a subset of the bits is going to be even as a permutation of a larger number of bits. $\endgroup$ – Ville Salo Jan 21 at 12:47
  • $\begingroup$ I've been thinking a bit about the permutation $x \mapsto x+1 \,\mathrm{mod}\, 2^n$. Is that a case you worked out? $\endgroup$ – François G. Dorais Jan 21 at 14:55
  • $\begingroup$ Isn't that an odd permutation? It has even variants of course, and I do not immediately have anything of interest to say about them. $\endgroup$ – Ville Salo Jan 21 at 15:05
  • $\begingroup$ What about any long cycle? $x \mapsto x+2 \,\mathrm{mod}\, 2^n$? $\endgroup$ – François G. Dorais Jan 21 at 15:32

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.


  • $\begingroup$ Stupid/subtle question about what "width" means. Is it (non-standardly?) the max number of edges that go through some horizontal cross-section when the graph is drawn with information coming from the top? If instead it is the max number of gates on a layer (as I think it's usually defined?), then 1) if all gates go from layer $i$ to $i+1$, you may need more than $O(k)$ gates since you have to copy the info on all layers; 2) if not all edges go from layer $i$ to $i+1$ but can jump any number of layers, then you can replace width $O(m+n)$ with width $O(1)$, since we're not bounding # of layers. $\endgroup$ – Ville Salo Jan 24 at 7:04
  • $\begingroup$ Yes. I am using that non-standard definition of "width.". $\endgroup$ – Joseph Van Name Jan 26 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.