Circuito polinomial reversible iff circuito polinomial reversible?

Mi pregunta es acerca de las funciones biyectivas computables de manera eficiente. Informalmente estoy interesado en:

Si una biyección es computable en tiempo polinómico, ¿podemos calcularla por un número polinómico de puertas biyectivas?

Revisé la lista de preguntas relevantes y no vi esta. Mi configuración precisa puede o no ser ortodoxa, así que incluyo mis definiciones. Creo que la pregunta es a nivel de investigación, pero estoy feliz de que me demuestren lo contrario.

Deje . Definamos una puerta como un elemento de para algún finito . Para finito, defina y defina . Para dos puertas escriba para la permutación definida por para , donde es concatenación de palabras. Para un conjunto de puertas escriba$B = \{0,1\}$A l t ( B n ) n N G N = ⋃ n ≤ N A l t ( B n ) G ∞ = ⋃ n A l t ( B n ) π 1 ∈ A l t ( B m ) , π 2 ∈ A l t ( B$\mathrm{Alt}(B^n)$$n$$N$$G_N = \bigcup_{n \leq N} \mathrm{Alt}(B^n)$$G_\infty = \bigcup_n \mathrm{Alt}(B^n)$$\pi_1 \in \mathrm{Alt}(B^m), \pi_2 \in \mathrm{Alt}(B^n)$$\pi = \pi_1 | \pi_2$$B^{m+n}$$\pi(u \cdot v) = \pi_1(u) \cdot \pi_2(v)$$u \in B^m, v \in B^n$$\cdot$$G$$\lceil G \rceil$ para el subconjunto más pequeño de contiene los mapas de identidad y se cierra bajo composiciones de funciones bien definidas , y bajo la operación.$\bigcup_n \mathrm{Alt}(B^n)$$(\pi_1, \pi_2) \mapsto \pi_1 \circ \pi_2$$|$

Se sabe que para todo , para la concreción. Concretamente, esto significa que cualquier para cualquier puede escribirse como para algunas , donde para cada existe y tal que para todos .$\lceil G_N \rceil = G_\infty$$N \geq 4$$N = 4$$\pi \in \mathrm{Alt}(B^n)$$n \geq N$$\pi = \phi_k \circ \cdots \circ \phi_2 \circ \phi_1$$k$$\phi_i$$\ell_i$$\pi_i \in \mathrm{Alt}(B^4)$$\phi_i(u \cdot v \cdot w) = u \cdot \pi_i(v) \cdot w$$|u| = \ell_i, |v| = 4$

Para una permutación par. Si , defina su complejidad de puerta reversible como el mínimo tal que pueda escribirse como una composición como la anterior. Si , defina la complejidad de la puerta de como . (Es posible que desee permitir la conjugación de puertas por las permutaciones por . Esto cambia la complejidad de la puerta solo por un factor lineal, por lo que para el presente propósito no importa).$\pi \in \mathrm{Alt}(B^n)$$n \geq 4$k π n < 4 π 1 u a b v ↦ u b a v$k$$\pi$$n < 4$$\pi$$1$$uabv \mapsto ubav$

Supongamos que tanto como su inverso son computables de manera eficiente en algún sentido, por ejemplo, tiempo polinomial, NC , espacio de registro ... ¿Es la complejidad de la puerta reversible de necesariamente polinomial? en ?$\pi \in \mathrm{Alt}(B^n)$d π n$^d$$\pi$$n$

Estoy interesado en una respuesta o referencias.

Algunas observaciones

• La prueba del teorema de Barrington muestra que para un fijo , si tiene la forma especial para alguna función , de modo que las permutaciones en las fibras son pares para cada , entonces la complejidad de la puerta reversible de es polinómica en siempre que esté en NC . Es decir, si hay un circuito NC para , entonces hay un circuito NC (más grande por un factor constante) con$m \geq 3$$\pi$$\pi(u \cdot w) = \psi(u, w) \cdot w$$\psi : B^m \times B^n \to B^m$$w$$\{u \cdot w \;|\; u \in B^m\}$$w \in B^n$$\pi$$n$$\pi$1 1 ψ 1 2 m ! / 2$^1$$^1$$\psi$$^1$$2^m!/2$ nodos de salida especiales que registran si se realizó una permutación particular en las primeras coordenadas . Entonces podemos mostrar (como en la prueba del teorema de Barrington) que para cada nodo en esta red, cada permutación incluso condicionada a cualquier valor de ese nodo, tiene una complejidad de circuito de tamaño polinómico en . Ahora combine los que corresponden a los nuevos nodos especiales para obtener una complejidad de puerta polinómica para .$m$$n$$\pi$

• El truco de Bennett muestra (entre otras cosas) que si y tienen una complejidad de puerta (computable por una red acíclica de puertas clásicas de dos entradas) , entonces hay permutación con polinomio de complejidad de puerta reversible en tal que para todos . Es decir, deje que calcule los valores de la red en los últimos bits, wrt alguna clasificación topológica de la red (suponiendo que sean ; de lo contrario, no nos importa). Dejar$\pi \in \mathrm{Alt}(B^n)$$\pi^{-1}$$m$$m$$\pi' \in \mathrm{Alt}s(B^{n+m})$$n + m$$\pi'(u \cdot 0^{n+m}) = (\pi(u) \cdot 0^{n+m})$$u \in B^n$$f$$m$$0$$g$nser el mapa que suma los bits de respuesta a los bits después de . Deje intercambiar la primera y segunda palabra de longitud . Entonces prueba la afirmación.$n$$n$$u$$h$$n$$h \circ f^{-1} \circ g \circ f$

• Las biyecciones unidireccionales en criptografía son permutaciones de , que tienen la propiedad de que pueden calcularse en tiempo polinomial, pero no pueden invertirse en tiempo polinomial. (Su propiedad definitoria es mucho más fuerte, pero no creo que sea relevante aquí.) No sé si esta definición particular tiene algo que ver directamente con el problema actual, ya que estamos tratando con un modelo de cálculo no uniforme .$B^n$

Sea ser una función. Luego defina una biyección dejando que . Entonces, si tiene una complejidad de puerta reversible , entonces puede calcularse mediante un circuito booleano de puerta de ancho . En otras palabras, tiene una baja complejidad de puerta reversible solo cuando es computable por un circuito de muy bajo ancho.$f:2^{m}\rightarrow 2^{n}$$L_{f}:2^{m}\times 2^{n}\rightarrow 2^{m}\times 2^{n}$$L_{f}(x,y)=(x,f(x)\oplus y)$$L_{f}$$k$$f$$O(k)$$m+n$$L_{f}$$f$