Reversible polynomial circuit = polynomial reversible circuit?

Question

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.

Answer 1

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

Answer 2

This is more of a comment, but did not fit.

Since I included "polynomial time" on my list of "easy to compute" properties, I realize (after almost a year) that @Joseph's is technically a perfectly good answer to an incarnation of my question, although not for the reasons I intended. I'll explain in what sense it is an answer, as far as I can tell, and I think I'll by default accept it (@Joseph's answer) in a few days unless I learn something new, I assume it is more or less what @Joseph had in mind, possibly with some complexity theory mistakes stacked on top, but since it's much longer and technical it didn't feel sensible to modify @Joseph's answer. There is a version of this question also on cstheory.SE, I think I'll just modify that one at some point to allow a bit less freedom, to exclude this type of "trivial" solution, and to clarify what I'm really after.

The class $\mathrm{DTISP}(f(n), g(n))$ for functions $f, g$ is the class of binary languages $L \subset \{0,1\}^*$ accepted by (deterministic, one work-tape, one read-only input tape) Turing machines using $f(n)$ time and $g(n)$ space. For sets of functions $F, G$, $\mathrm{DTISP}(F,G) = \bigcup_{f \in F, g \in G} \mathrm{DTISP}(f, g)$. Define also $\mathrm{poly} = \bigcup_d O(n^d)$.

Let's call $\mathrm{DTISP}(\mathrm{poly},n)/\mathrm{poly}$, or non-uniform linear space polynomial time in words, the (Turing machine) polynomial-time linear space computable languages with polynomial advice (given on a separate tape with (equivalently) one- or two-way read-only access). This is, I believe, the same as linear width (for the standard notion of width, i.e. number of stored bits = nodes per layer, and all wires go from one layer to the next) polynomial depth circuits, with the following reasoning: Simulating circuits by $\mathrm{DTISP}(\mathrm{poly},n)/\mathrm{poly}$ is a standard thing, read a description of the circuit layer by layer and use your space to store a layer and a buffer for the next layer. Simulating $\mathrm{DTISP}(\mathrm{poly},n)/\mathrm{poly}$ by circuits has the technical hurdle that you cannot include the advice into the circuit, but you can use the following trick: observe that we may assume a $\mathrm{DTISP}(\mathrm{poly},n)/\mathrm{poly}$ Turing machine, on its advice tape, walks at constant speed to the right. With a bit of timing trickery and a periodic advice tape we can still read the desired bits of advice (with at most polynomial time-blow-up and constant space blow-up). Then draw a generic Turing machine spacetime diagram as a circuit as usual, and when the head reads advice the advice depends only on the depth of the current layer, so this is easy to incorporate into the circuit.

Let's write $B$ for the class of functions I'm interested in, more specifically the family of sequences of functions $(f_n)_n$, $f_n : \{0,1\}^n \to \{0,1\}^n$, which are accepted by (a non-uniform family of) polynomial-length compositions of the basic reversible gates.

Now, @Joseph's construction conditionally solves the following incarnation of my question (polynomial is interpreted in the nonuniform sense over $n$, i.e. for some polynomial $p(n)$, you have a family of bijections computed in time $p(n)$ (so in nonuniform FP) and the answer gives a family of reversible circuits of size $q(n)$ as answer):

Suppose that both $\pi \in \mathrm{Alt}(B^n)$ and its inverse are polynomial time computable. Is the reversible gate complexity of $\pi$ then necessarily polynomial in $n$?

Here's the conditional answer:

If there is a language in $\mathrm{P}/\mathrm{poly} \setminus \mathrm{DTISP}(\mathrm{poly}, n)/\mathrm{poly}$, then there exists a family of functions $g_n : \{0,1\}^n \to \{0,1\}^n$ such that $(g_n)_n$ and $(g_n^{-1})_n$ are in $(G_n)_n \cap \mathrm{nonuniform\;FP}$, but $(g_n)_n \notin B$.

Proof. Let $L \in \mathrm{P}/\mathrm{poly} \setminus \mathrm{DTISP}(\mathrm{poly}, n)/\mathrm{poly}$ and for $n \in \mathbb{N}$ let $f_n : \{0,1\}^n \to \{0,1\}$ be the indicator function of $L \cap \{0,1\}^n$. Construct $g_n : \{0,1\}^{n+1} \to \{0,1\}^{n+1}$ as in @Joseph's answer. It's clearly still nonuniform polynomial time (for the same polynomial) and since it is an involution, so is $g_n^{-1}$. Now, assuming the answer to the above incarnation of my question is "yes", then $g_n$ admits a size $q(n)$ reversible circuit. Then the "subcircuit" that fixes the last bit of input to $0$ and computes only the last bit is clearly in $\mathrm{DTISP}(\mathrm{poly}, n)/\mathrm{poly}$ (reversible gates can be simulated with classical ones of course). But clearly this subcircuit is a circuit for $L \cap \{0,1\}^n$, and we have shown $L \in \mathrm{DTISP}(\mathrm{poly}, n)/\mathrm{poly}$, a contradiction. QED

Now, do we expect $\mathrm{P}/\mathrm{poly} \setminus \mathrm{DTISP}(\mathrm{poly}, n)/\mathrm{poly} \neq \emptyset$ to be true? I would conjecture yes, here's the first heuristic: Let's write $A \overset{C}\subset B$ for "conjecturally $A \subset B$", where $C$ is a conjecture identifier, and similarly for other set comparisons.

• While it is known that $\mathrm{P} \neq \mathrm{DSPACE}(n)$, neither inclusion is known, and it has been conjectured that the classes are incomparable. In particular we have $\mathrm{P} \setminus \mathrm{DSPACE}(n) \overset{SA}{\neq} \emptyset$.
• By definition $\mathrm{DTISP}(\mathrm{poly}, n)/\mathrm{poly} \subset \mathrm{DSPACE}(n)/\mathrm{poly}$
• "Division by poly" in $\mathrm{P} \setminus \mathrm{DSPACE}(n) \overset{SA}{\neq} \emptyset$" gives $\mathrm{P}/\mathrm{poly} \setminus \mathrm{DSPACE}(n)/\mathrm{poly} \overset{VS}{\neq} \emptyset$", and then $\mathrm{P}/\mathrm{poly} \setminus \mathrm{DTISP}(\mathrm{poly}, n)/\mathrm{poly} \overset{VS}{\neq} \emptyset$ a fortiori, as desired.

The conjecture $\mathrm{P} \overset{SA}{\setminus} \mathrm{DSPACE}(n) \neq \emptyset$ can be found in How do we know that P != LINSPACE without knowing if one is a subset of the other? and I have a hunch that it's not easy to refute, as $SA$ tends to be quite strong. The division by poly step on the other hand is nothing but mathematical humor (as far as I can tell), I don't see what we should expect to happen when you add the advice.

Here's another heuristic. If we ignore the nonuniformity issues (so it's easier to find information - I don't understand the subtle subtleties anyway), $\mathrm{P} \setminus \mathrm{DTISP}(\mathrm{poly}, n) \neq \emptyset$ is of course a much weaker claim than $\mathrm{P} \setminus \mathrm{DSPACE}(n) \neq \emptyset$, since you have both a space and a time bound. One might think then that the noninclusion is actually provable: we need to show $\mathrm{P} = \mathrm{DTISP}(\mathrm{poly}, \mathrm{poly}) \setminus \mathrm{DTISP}(\mathrm{poly}, n)$ and we know that it is unconditionally true that $\mathrm{DSPACE}(\mathrm{poly}) \setminus \mathrm{DSPACE}(n) \neq \emptyset $! Well, if you go through with the usual proof, you see that the quantification over poly comes at an unfortunate time, and it doesn't go through. (Prove me wrong!) Still, perhaps it adds credibility to the conjecture.