Circuito complejo de función mayoritaria

Sea la función mayoritaria, es decir, si y solo si . Me preguntaba si había una prueba simple del siguiente hecho (por "simple" me refiero a no confiar en el método probabilístico como Valiant 84 o en redes de clasificación; preferiblemente proporcionando una construcción explícita y directa del circuito):$f: \{0,1\}^n \to \{0,1\}$$f(x) = 1$$\sum_{i = 1}^n x_i > n/2$

$f$ puede calcularse mediante una familia de circuitos de profundidad , tamaño poli (n), donde las compuertas consisten en compuertas NO, compuertas OR de 2 entradas y compuertas AND de 2 entradas.$O(\log(n))$

La respuesta de Kaveh proporciona una respuesta para hacer la pregunta como la ha dicho (y esta es la prueba habitual para demostrar que está contenido en N C 1 ). Pero estaba pensando que en realidad podrías haber intentado hacer una pregunta un poco diferente. A saber, para una fórmula monótona de tamaño polinómico explícito para la mayoría.$\mathsf{TC}^0$$\mathsf{NC}^1$

Como la mayoría es monótona, sabemos que se puede calcular mediante una fórmula monótona. Hay dos construcciones conocidas de fórmulas monótonas de tamaño polinómico, a saber, las dos que mencionas, la construcción probabilística de Valiant y la construcción a través de redes de clasificación. Hasta donde sé, no tenemos una construcción determinista más simple que la que proporcionan las redes de clasificación.

Relacionado con esto también está lo siguiente. Resulta que la mayoría puede calcularse mediante fórmulas que consisten en solo puertas (¡y sin constantes!). La construcción probabilística de Valiant se puede adaptar para dar tales fórmulas de profundidad O ( log ( n ) ) . Sin embargo, aquí no conocemos ninguna construcción determinista. En particular, las redes de clasificación no son adecuadas para esto (razón técnica: proporcionarían todas las funciones de umbral y solo la función mayoritaria puede ser calculada en absoluto por las puertas M A J 3 ). Sin embargo, hay avances recientes sobre esta cuestión en el documento$\mathsf{MAJ}_3$$O(\log(n))$$\mathsf{MAJ}_3$Protocolos multiparte eficientes mediante fórmulas de umbral de profundidad logarítmica de Cohen et al. Aquí tales fórmulas son construcciones basadas en supuestos estándar de complejidad teóricos o criptográficos.

El cálculo de la puerta de umbral restringida ( ) es esencialmente la clasificación de bits de entrada.$\sum_i x_i \geq k$

Si puede ordenar los bits, entonces es fácil comparar el resultado con y calcular el umbral restringido.$k$

Por otro lado, suponga que tenemos un circuito para calcular el umbral restringido. Podemos hacer una búsqueda paralela para encontrar el número de unidades en la entrada y salida de la lista ordenada.

Estos preservan la profundidad del circuito. Entonces, si se te ocurre un nuevo circuito para calcular el umbral restringido, entonces dará un circuito de clasificación de profundidad O ( lg n ) . Entonces, si encontramos un argumento simple para mostrar que la mayoría está en N C 1 , ha encontrado un circuito de clasificación simple de profundidad O ( lg n ) (distinto del que se basa en la red de clasificación AKS).$\mathsf{NC^1}$$O(\lg n)$$\mathsf{NC^1}$$O(\lg n)$

Tenga en cuenta que es fácil implementar el umbral restringido utilizando mayoría agregando nuevas entradas 1 y 0 a la puerta de mayoría.

$\mathsf{AC^0}$$\mathsf{AC^1}$$\mathsf{NC^2}$

$O(\lg n)$

$a,b,c$$x,y$$a+b+c = x+y$

$O(1)$

Ver sección 4 y ejercicio 4 en

• David Mix Barrington y Alexis Maciel, " Curso avanzado sobre complejidad computacional ", conferencia 6, IAS / PCMI, 2000.

$n$

Brodal y Husfeldt ofrecen una prueba alternativa: una prueba de la complejidad de la comunicación de que las funciones simétricas tienen profundidad logarítmica . Nuevamente, la prueba es elemental y proporciona una construcción explícita.