Decidir si un circuito dado calcula una permutación

¿Cuál es la complejidad de decidir si un circuito con bits de entrada y bits de salida calcula una permutación de ? en otras palabras, si cada cadena de bits en es una salida del circuito para alguna entrada? Parece un problema que ha sido estudiado, pero no puedo encontrar ninguna referencia. nn{0,1 } n {0,1 } $\mathsf{NC}^0$$n$$n$$\{0,1\}^n$$\{0,1\}^n$

Dureza

Después de su comentario sobre la pregunta, llamaremos a un circuito donde cada bit de salida depende de a lo sumo k bits de entrada como un " circuito NC ⁰ _k ". Usando este término, su problema es completo en caso de circuitos NC ⁰ ₅ . Es decir, el siguiente problema es coNP-complete.

Instancia : Un circuito booleano C con n bits de entrada y n bits de salida donde cada bit de salida depende de, como máximo, cinco bits de entrada.
Pregunta : ¿El mapeo de {0,1} ⁿ a sí mismo es calculado por C bijective?

Como comentó Kaveh, está claramente en coNP, incluso sin el límite en el número de bits de entrada de los que depende cada bit de salida. Para probar la dureza de coNP, reduciremos 3SAT al complemento del problema actual. La idea clave de la reducción es la misma que la utilizada en el artículo [Dur94] de Durand, que mencioné en un comentario sobre la pregunta, pero la reducción total es mucho más simple en nuestro caso.

Dada una fórmula 3CNF φ con n variables y m cláusulas, construimos un circuito booleano C con ( n + m bits de entrada) y ( n + m bits de salida) como sigue. Rotulamos los bits de entrada como x ₁ , ..., x _n , y ₁ , ..., y _m , y los bits de salida como x ′ ₁ , ..., x ′ _n , z ₁ , ..., z _m . Consideramos que los bits de entrada x₁ , ..., x _n especifica una asignación de verdad a las n variables en φ .

• x ′ _i = x _i para 1≤ i ≤ n . Es decir, los primeros n bits de entrada siempre se copian a los primeros n bits de salida.
• Para 1≤ i ≤ m , si se cumple la i ésima cláusula de φ , entonces z _i = y _i ⊕ y _{i +1} , donde el subíndice se interpreta módulo m . De lo contrario, z _i = y _i .

Tenga en cuenta que cada bit de salida depende de como máximo cinco bits de entrada. Omito la prueba de la corrección de la reducción, pero la idea clave (que tomé prestada de [Dur94]) es que si φ es satisfactoria y los bits de entrada x ₁ , ..., x _n se establecen en una asignación satisfactoria de φ , entonces los m bits de salida z ₁ , ..., z _m están obligados a tener la paridad par y, por lo tanto, el circuito no puede ser una permutación. Por otro lado, si los bits de entrada x ₁ , ..., x _n se configuran en una asignación no satisfactoria de φ , entonces los bits de salida z₁ , ..., z _m se puede establecer en cualquier cosa; debido a esto, si φ es insatisfactorio, entonces el circuito es una permutación.

Trazabilidad

En el lado manejable, su problema está en P en el caso de los circuitos NC ⁰ ₂ . Esto se muestra a continuación. En general, cada bit de salida en un circuito booleano para una permutación está equilibrado ; es decir, exactamente la mitad de las cadenas de entrada establecen el bit de salida en 1. Sin embargo, cada función booleana equilibrada de {0,1} ² a {0,1} es afín ; es decir, una copia de un solo bit de entrada, el XOR de los dos bits de entrada o la negación de ellos. Por lo tanto, primero podemos verificar que cada bit de salida esté equilibrado, y luego verificar la biyectividad mediante la eliminación gaussiana.

No conozco la complejidad en el caso de los circuitos NC ⁰ ₃ o en el caso de los circuitos NC ⁰ ₄ .

Referencias

[Dur94] Bruno Durand. Inversión de autómatas celulares 2D: algunos resultados de complejidad. Informática teórica , 134 (2): 387–401, noviembre de 1994. DOI: 10.1016 / 0304-3975 (94) 90244-5 .