Circuito complejo de función mayoritaria

13

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{0,1}f(x)=1i=1nxi>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))

Matthon
fuente
66
Esto podría ser de interés: Igor Sergeev, límites superiores para el tamaño de la fórmula de la función mayoritaria ; También aquí anuncia límites superiores ligeramente mejores. Sin embargo, si pregunta por solo circuitos (no fórmulas ), entonces, como me recordó Igor, cada función booleana simétrica (no solo la mayoría) tiene un circuito de profundidad y tamaño : solo calcule la suma de s, y realizar una función booleana de variables. Para la mayoría, esta última función es una comparación con . O(logn)O(n)1log2nn/2
Stasys
@Stasys, y calcular el número de unidades es esencialmente ordenar los bits.
Kaveh

Respuestas:

9

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.TC0NC1

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 documentoMAJ3O(log(n))MAJ3Protocolos 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.

Kristoffer Arnsfelt Hansen
fuente
9

El cálculo de la puerta de umbral restringida ( ) es esencialmente la clasificación de bits de entrada.ixik

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).NC1O(lgn)NC1O(lgn)

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.


AC0AC1NC2

O(lgn)


a,b,cx,ya+b+c=x+y

O(1)

Ver sección 4 y ejercicio 4 en

Kaveh
fuente
O(lgn)O(lgn)