Decidir si un circuito NC calcula una permutación o no

Quisiera preguntar sobre un caso especial de la pregunta " Decidir si un circuito NC ^{0 determinado} calcula una permutación " por QiCheng que no se ha respondido.

Un circuito booleano se denomina circuito NC ⁰ _k si cada puerta de salida depende sintácticamente de, como máximo, k puertas de entrada. (Decimos que una puerta de salida g depende sintácticamente de una puerta de entrada g 'cuando hay una ruta dirigida de g ' a g en el circuito como se ve como un gráfico acíclico dirigido).

En la pregunta antes mencionada, QiCheng preguntó sobre la complejidad del siguiente problema, donde k es una constante:

Instancia : Un NC ⁰ _k circuito con n entrada de bits y n salida de bits.
Pregunta : ¿El circuito dado calcula una permutación en {0, 1} ⁿ ? En otras palabras, ¿la función calculada por el circuito es una biyección de {0, 1} ⁿ a {0, 1} ⁿ ?

Como Kaveh comentó sobre esa pregunta, es fácil ver que el problema está en coNP. En una respuesta, mostré que el problema es completo para k = 5 y que está en P para k = 2.

Cuestión . ¿Cuál es la complejidad para k = 3?

Aclaración el 29 de mayo de 2013 : “Una permutación en {0, 1} ⁿ ” significa un mapeo biyectivo de {0, 1} ⁿ a sí mismo. En otras palabras, el problema pregunta si cada cadena de n bits es la salida del circuito dado para alguna cadena de entrada de n bits.

Este problema con es coNP-hard (y por lo tanto coNP-complete).$k=3$

Para probar esto, de 3-SAT al complemento de este problema (para un circuito dado , el circuito promulga una función no biyectiva).$NC_3^0$

Primero una definición preliminar que será útil:

Definimos un gráfico etiquetado como un gráfico dirigido, algunos de cuyos bordes están etiquetados con literales, con la propiedad de que cada vértice tiene un borde entrante sin etiquetar, un borde entrante etiquetado o dos bordes entrantes sin etiquetar.

La reducción

Supongamos que tenemos una fórmula 3-SAT consta de cláusulas, cada una con tres literales. El primer paso es construir un gráfico etiquetado partir de . Este gráfico etiquetado contiene una copia del siguiente gadget (perdón por el terrible diagrama) para cada cláusula en . Los tres bordes etiquetados como L1, L2 y L3 están etiquetados con los literales en la cláusula.m G ϕ $\phi$$m$$G$$\phi$$\phi$

   |
   |               |
   |               |
   |               O<-----\
   |               ^      |
   |               |      |
   |               |      |
   |        /----->O      |
   |        |      ^      |
   |        |      |      |
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |L1    |L2    |L3
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |      |      |
   |        \------O------/
   |               ^
   |               |
   |               |
   |               O
   |               ^
   |               |
   |

Los gadgets (uno para cada cláusula) se organizan en un gran ciclo con la parte inferior de un gadget unida a la parte superior del siguiente.

Tenga en cuenta que esta disposición de gadgets de hecho forma un gráfico etiquetado (cada vértice tiene un grado 1 o 2 con solo bordes que conducen a vértices del grado 1 etiquetados).

A partir de la fórmula y el gráfico etiquetado (que se construyó a partir de ), a continuación construimos un circuito (esto concluirá la reducción). El número de entradas y salidas de este circuito es , donde es el número de variables en y es el número de vértices en . Una entrada y una salida se asigna a cada variable en y para cada vértice en . Si es alguna variable en , nos referiremos a los bits de entrada y salida asociados con comoG ϕ N C 0 3 n + v n ϕ v G ϕ G x ϕ x x i n x o u t l l = x l i n = x i n l l = ¬ x l i n = ¬ x i n v G v v i n v o u $\phi$$G$$\phi$$NC_3^0$$n+v$$n$$\phi$$v$$G$$\phi$$G$$x$$\phi$$x$$x_{in}$ y . Además, si es un literal con entonces definimos y si es un literal con entonces definimos . Finalmente, si es algún vértice en , nos referiremos a los bits de entrada y salida asociados con como y .$x_{out}$$l$$l = x$$l_{in} = x_{in}$$l$$l = \neg x$$l_{in} = \neg x_{in}$$v$$G$$v$$v_{in}$$v_{out}$

Hay cuatro tipos de bits de salida:

1) Para cada variable in , . Tenga en cuenta que esta salida depende de un solo bit de entrada.ϕ x o u t = x i $x$$\phi$$x_{out} = x_{in}$

2) Para cada vértice en el gráfico etiquetado con exactamente un borde entrante modo que el borde no esté etiquetado, . Tenga en cuenta que esta salida depende de solo dos bits de entrada.( u , v ) v o u t = v i n ⊕ u i $v$$(u, v)$$v_{out} = v_{in} \oplus u_{in}$

3) Para cada vértice en el gráfico etiquetado con exactamente un borde entrante modo que el borde esté etiquetado como , . Tenga en cuenta que esta salida depende de solo tres bits de entrada, ya que depende solo de para cualquier variable utilizada en el literal .( u , v ) l v o u t = v i n ⊕ ( u i n ∧ l i n ) l i n x i n x $v$$(u, v)$$l$$v_{out} = v_{in} \oplus (u_{in} \land l_{in})$$l_{in}$$x_{in}$$x$$l$

4) Para cada vértice en el gráfico etiquetado con exactamente dos bordes entrantes y , . Tenga en cuenta que esta salida depende de solo tres bits de entrada.( u , v ) ( w , v ) v o u t = v i n ⊕ ( u i n ∨ w i n$v$$(u, v)$$(w, v)$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$

Como en todos los casos la salida depende de solo tres entradas, el circuito que construimos está en como se desee.$NC_3^0$

Prueba de corrección caso 1: es satisfactoria$\phi$

Supongamos que existe una asignación satisfactoria para . Luego construya los siguientes dos conjuntos de valores para las entradas.$\phi$

1) Las entradas asociadas con las variables de reciben los valores de la asignación satisfactoria. Todas las entradas asociadas con vértices de reciben el valor 0.$\phi$$G$

2) Las entradas asociadas con las variables de reciben los valores de la asignación satisfactoria. Considere los vértices en un gadget cláusula en . Si el valor de una etiqueta es 0 (bajo la asignación satisfactoria), la entrada asociada con el vértice en el punto final objetivo del borde etiquetado con esa etiqueta tiene un valor de 0. Si L1 y L2 tienen el valor 0, entonces el segundo -vértice superior en el gadget (como se muestra arriba) también tiene un valor de 0. Todos los demás vértices tienen un valor de 1.$\phi$$G$

Queremos mostrar que estos dos conjuntos de entradas producen salidas idénticas y, por lo tanto, que el circuito no codifica una permutación.$NC_3^0$

Considere los cuatro tipos de bits de salida:

1) Para cada variable in , . Como es igual para ambos conjuntos de entradas, las salidas de esta forma siempre serán las mismas en los dos conjuntos de entradas.$x$$\phi$$x_{out} = x_{in}$$x_{in}$

2) Para cada vértice en el gráfico etiquetado con exactamente un borde entrante modo que el borde no esté etiquetado, . Al examinar el dispositivo cuyas copias componen , vemos que todos esos bordes consisten solo en pares de vértices cuyos valores de entrada son siempre 1 bajo el segundo conjunto de entradas. Por lo tanto, bajo el primer conjunto de entradas y bajo el segundo conjunto de entradas. Por lo tanto, las salidas de esta forma siempre serán las mismas (y de hecho cero) en los dos conjuntos de entradas.$v$$(u, v)$$v_{out} = v_{in} \oplus u_{in}$$G$$v_{out} = v_{in} \oplus u_{in} = 0 \oplus 0 = 0$$v_{out} = v_{in} \oplus u_{in} = 1 \oplus 1 = 0$

3) Para cada vértice en el gráfico etiquetado con exactamente un borde entrante modo que el borde esté etiquetado como , . Si es falso bajo la asignación, entonces es 0 bajo ambos conjuntos de entradas; entonces en ambos conjuntos de entradas. Si es verdadero bajo la asignación, es 0 bajo el primer conjunto de entradas y 1 bajo el segundo; También tenga en cuenta que en el gadget, los únicos bordes etiquetados tienen vértices que siempre tienen$v$$(u, v)$$l$$v_{out} = v_{in} \oplus (u_{in} \land l)$$l$$v_{in}$$v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 0) = v_{in} = 0$$l$$v_{in}$$(u, v)$$u$$u_{in} = 1$ bajo el segundo conjunto de entradas. Como resultado, vemos que bajo ambos conjuntos de entradas, siempre que sea ​​verdadero; entonces . Por lo tanto, las salidas de esta forma siempre serán las mismas (y de hecho cero) en los dos conjuntos de entradas.$u_{in} = v_{in}$$l$$v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 1) = v_{in} \oplus u_{in} = v_{in} \oplus v_{in} = 0$

4) Para cada vértice en el gráfico etiquetado con exactamente dos bordes entrantes y , . Hay dos vértices en cada gadget. El vértice superior y el segundo vértice superior. Consideramos esos dos casos por separado.$v$$(u, v)$$(w, v)$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$

4a) Cuando es el segundo vértice superior en un gadget, y son los dos puntos finales objetivo de los bordes etiquetados como L1 y L2. En el primer conjunto de entradas, . Bajo el segundo conjunto de entradas, es 0 si L1 tiene el valor 0 bajo la asignación satisfactoria (también como ); de manera similar, es 0 si L2 tiene el valor 0 bajo la asignación satisfactoria (también como ); y finalmente, se define como 0 si L1 y L2 tienen el valor 0 (también conocido como ). Así, bajo el segundo conjunto de entradas,$v$$u$$w$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$$u_{in}$$u_{in} = L1$$w_{in}$$w_{in} = L2$$v_{in}$$v_{in} = L1 \lor L2$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = (L1 \lor L2) \oplus (L1 \lor L2) = 0$ . Por lo tanto, las salidas de esta forma siempre serán las mismas (y de hecho cero) en los dos conjuntos de entradas.

4b) Cuando es el vértice superior de un dispositivo, es el segundo vértice superior y es el punto final objetivo del borde etiquetado como L3. En el primer conjunto de entradas, . Bajo el segundo conjunto de entradas, es 0 si L1 y L2 tienen el valor 0 (también como ); es 0 si L3 tiene el valor 0 (también como ); y finalmente . Por lo tanto, bajo el segundo conjunto de entradas, donde la igualdad$v$$u$$w$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$$u_{in}$$u_{in} = L1 \lor L2$$w_{in}$$w_{in} = L3$$v_{in} = 1$$v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 1 \oplus ((L1 \lor L2) \lor L3) = 1 \oplus (L1 \lor L2 \lor L3) = 1 \oplus 1 = 0$$(L1 \lor L2 \lor L3) = 1$ mantiene por definición en una asignación satisfactoria para cada cláusula. Por lo tanto, las salidas de esta forma siempre serán las mismas (y de hecho cero) en los dos conjuntos de entradas.

Claramente, vemos que las salidas son las mismas para dos conjuntos diferentes de entradas y, por lo tanto, que el circuito realiza una función no biyectiva.$NC_3^0$

Prueba de corrección caso 2: es insatisfactorio$\phi$

Supongamos ahora que no existe una asignación satisfactoria para . Luego, supongamos, en aras de la contradicción, que unos dos conjuntos diferentes de entradas conducen al circuito que tiene la misma salida.$\phi$$NC_3^0$

Claramente, las dos entradas deben tener los mismos valores para para cada variable en . Por lo tanto, ahora podemos referirnos sin ambigüedad al valor de .$x_{in}$$x$$\phi$$x$

Defina como el conjunto de vértices en modo que sea ​​diferente en los dos conjuntos de valores de entrada.$S$$v$$G$$v_{in}$

A continuación demostraremos los siguientes lemas:

Lema 1: Si en algún aparato los tres vértices en los puntos finales de destino de los bordes marcados no están en entonces no hay vértices superiores a los tres de la herramienta están en .$S$$S$

Lema 2: Si en algún aparato el vértice superior no está en a continuación, en el siguiente aparato hasta ningún vértice está en .$S$$S$

Dado que los gadgets forman un bucle, esto implica que si en cualquier gadget los tres vértices en los puntos finales de destino de los bordes etiquetados no están en entonces ningún vértice en está en (en otras palabras, está vacío).$S$$G$$S$$S$

Sin embargo, considere un dispositivo asociado con una cláusula que no está satisfecho. En este gadget, las tres etiquetas tienen un valor 0. Sabemos que el borde etiquetado como debe satisfacer , pero , entonces . Por lo tanto, dado que la salida es la misma para ambas entradas, los valores de también deben ser los mismos en los dos conjuntos de entradas. En otras palabras, hemos demostrado que no está en$(L1 \lor L2 \lor L3)$$(u, v)$$L$$v_{out} = v_{in} \oplus (u_{in} \land L)$$L = 0$$v_{out} = v_{in} \oplus (u_{in} \land L) = v_{in} \oplus (u_{in} \land 0) = v_{in} \oplus 0 = v_{in}$$v_{in}$$v$$S$. Así vemos que en este dispositivo particular, los tres vértices en los puntos finales de destino de los bordes marcados no están en .$S$

Como resultado, concluimos que está vacío. Sin embargo, esto implica que entre los dos conjuntos de entradas, no hubo diferencias, lo que contradice el supuesto de que estos conjuntos de entradas son diferentes. Como resultado, vemos que la función realizada por el circuito es inyectiva y, por lo tanto, una biyección.$S$$NC_3^0$

Todo lo que queda es probar los lemas.

Para hacer esto, notamos que para cada tipo de vértice en (grado 1 con etiqueta, grado 1 sin etiqueta y grado 2), si todos los bordes entrantes provienen de vértices que no están en entonces el vértice en cuestión tampoco está en . Esto se debe a que en los tres casos donde es alguna función de las entradas asociadas con variables y / o vértices con aristas a . Dado que todos estos vértices no están en por suposición, el valor de debe ser el mismo en ambos conjuntos de entradas. Por lo tanto, también es el mismo en ambos conjuntos de entradas. En otras palabras$G$$S$$S$$v_{out} = v_{in} \oplus X$$X$$v$$S$$X$$v_{in} = v_{out} \oplus X$$v$no está en .$S$

Ahora que tenemos la regla de que un vértice no está en cuando todos sus predecesores no están en , los lemas siguen simplemente aplicando la regla repetidamente al diagrama de gadgets anterior.$S$$S$

No es la respuesta que buscaba el autor, vea los comentarios que aclaran qué es "permutación" en este contexto.

Creé el tamaño del conjunto dominante mínimo para el dígrafo de inclusión del grupo de permutación monogénica: https://oeis.org/A186202

Todo lo que tiene que hacer es probar un miembro de cada descomposición del ciclo principal.

Para cada ciclo principal, debería ser suficiente codificar los elementos como (10101010 ...), luego (01010101 ..)?

------ Aclaración ------ El objetivo de este enfoque es modelar sus 2 ^ n casos de prueba como un dígrafo. Si un caso de prueba exitoso implica otro caso de prueba exitoso, entonces solo tiene que probar el conjunto dominante mínimo de este dígrafo espacial de prueba. En el espacio de permutaciones, OEIS A186202 es el máximo que debe probar para detectar un subgrupo no trivial o demostrar que no existe; este número sigue siendo grande pero mucho más pequeño que n !.

--Musing-- Al usar n-1 ceros y 1 uno en n iteraciones, puede detectar la permutación fija que está buscando. Después de eso, en O (n {(n-1) \ choose (k-1)} (2 ^ (k-1)) puede probar que cada conjunto de variables (k-1) no afecta a cada índice del shuffle Como k es fijo, eso es polinomial. ¿Me estoy perdiendo algo?