Razborov demostró que la coincidencia de la función monótona no está en mP . Pero, ¿podemos calcular la correspondencia utilizando un circuito de tamaño polinómico con algunas negaciones? ¿Hay un circuito P / poly con negaciones que calcule la coincidencia? ¿Cuál es la compensación entre el número de negaciones y el tamaño de la coincidencia?$O(n^\epsilon)$

Markov demostró que cualquier función de $n$ entradas se puede calcular con solo $\lceil \log (n+1)\rceil$ negaciones. Fisher describió una versión constructiva eficiente. Vea también una exposición del resultado del blog GLL .

Más precisamente:

Teorema: supongamos que se calcula mediante un circuito C con puertas g , luego también se calcula mediante un circuito C ∗ con 2 g + O ( n 2 log 2 n ) puertas y ⌈ log ( n + 1 ) ⌉ negaciones.$f : \{0,1\}^n \to \{0,1\}^m$$C$$g$$C^*$$2g + O(n^2 \log^2 n)$$\lceil \log (n+1) \rceil$

La idea principal es agregar para cada cable en C un cable paralelo w ' en C ∗ que siempre lleva el complemento de w . El caso base es para los cables de entrada: Fisher describe cómo construir un circuito de inversión I ( x ) = ¯ x con puertas O ( n 2 log 2 n ) y solo ⌈ log ( n + 1 ) ⌉ negaciones. Para las puertas Y del circuito C , podemos aumentar $w$$C$$w'$$C^*$$w$$I(x) = \overline x$$O(n^2 \log^2 n)$$\lceil \log (n+1) \rceil$$C$ con a ′ = b ′ ∨ c ′ , y lo mismo para las puertas OR. Las puertas NOT en C no cuestan nada, solo intercambiamos los roles de w y w ' aguas abajo de la puerta NOT. De esta manera, todo el circuito además del subcircuito inversor es monótono.$a = b \land c$$a' = b' \lor c'$$C$$w$$w'$

AA Markov. Sobre la complejidad de inversión de un sistema de funciones. J. ACM , 5 (4): 331–334, 1958.

MJ Fischer. La complejidad de las redes de negación limitada: una breve encuesta. En teoría de autómatas y lenguajes formales , 71–82, 1975

Cómo calcular la inversión de bits usando n negaciones$2^n-1$$n$

Deje que los bits se ordenen en orden decreciente, es decir, i < j implica x i ≥ x j . Esto se puede lograr mediante una red de clasificación monótona como la red de clasificación Ajtai – Komlós – Szemerédi.$x_0, \ldots, x_{2^n-1}$$i<j$$x_i \ge x_j$

Definimos el circuito de inversión para bits I n ( → x ) inductivamente: Para el caso base tenemos n = 1 e I 1 0 ( → x ) : = ¬ x 0 . Sea m = 2 n - 1 . Reducimos I n (para 2 m + 1 ) bits a una I n - 1 puerta (para $2^n-1$$I^n(\vec{x})$$n=1$$I^1_0(\vec{x}) := \lnot x_0$$m=2^{n-1}$$I^n$$2m+1$$I^{n-1}$$m$bits) y una puerta de negación con y ∨ puertas. Usamos la negación para calcular ¬ x m . Para i < m let y i : = ( x i ∧ ¬ x m ) ∨ x m + i . Usamos I n - 1 para invertir → y . Ahora podemos definir I n de la siguiente manera:$\land$$\lor$$\lnot x_m$$i<m$$y_i := (x_i \land \lnot x_m) \lor x_{m+i}$$I^{n-1}$$\vec{y}$$I^n$

Es fácil verificar que esto invierte considerando los posibles valores de x ny utilizando el hecho de que → x está disminuyendo.$\vec{x}$$x_n$$\vec{x}$

De Michael J. Fischer, La complejidad de las redes de negación limitada: una breve encuesta, 1975.