¿Los circuitos de profundidad 2 con compuertas OR y MOD no son universales?

Es bien sabido que cada función booleana puede realizarse utilizando un circuito booleano de profundidad 2 (sobre las variables, su negación y sus valores constantes) que contiene compuertas AND en el primer nivel y una compuerta OR simple en el nivel superior; esto es simplemente la representación DNF de . $f:\{0,1\}^n\to \{0,1\}$ $f$

Otro tipo de puerta que es de gran interés en la complejidad del circuito es la puerta . La definición habitual es la siguiente: $MOD_m$

{M O D}_{m} (x_{1}, \dots, x_{k}) = {\begin{cases} 1 & if \sum x_{i} \equiv 0 \mod m \\ 0 & if \sum x_{i} ≢ 0 \mod m \end{cases}

$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{ 1 & if $\sum x_i \equiv 0 \mod m$ \\ 0 & if $\sum x_i \not\equiv 0 \mod m$ \\ }$

Estas puertas a veces tienen un poder sorprendente; por ejemplo, cualquier función booleana se puede representar mediante un circuito de profundidad 2 que solo tiene $\mathrm{MOD}_6$ puertas (esto es folklore pero puedo explicar si alguien está interesado).

Sin embargo, otro folklore es que los circuitos con una sola puerta OR en la parte superior y las puertas $\mathrm{MOD}_m$ en la capa inferior (con $m$ fijado de una vez por todas, y en particular siendo el mismo para todas las puertas) no es universal, es decir, para cualquier valor de $m$ , hay funciones booleanas que no pueden ser calculadas por el circuito $\mathrm{OR} \circ \mathrm{MOD}_m$ .

Estoy buscando una prueba para este reclamo, o al menos alguna dirección.

complexity-theory logic circuits Gadi A
fuente

En el primer párrafo, NO necesita puertas o tiene que decir "cada función booleana monótona ".

Tsuyoshi Ito

Estás en lo correcto; La suposición habitual es que tiene como entradas las variables, su negación y también los valores arbitrarios (importantes para los modgates). Escribiré esto explícitamente.

Gadi A

Supongo que , el número de variables de entrada, es diferente de , ¿el módulo?

n

$n$

n

$n$

Kristoffer Arnsfelt Hansen

Sí, perdón por eso.

Gadi A

Estoy interesado en esto ¿Conoces alguna referencia para el primer hecho folklórico? Me pregunto, si en la última clase de circuitos solo permite un OR, ¿cuántos permite en el primero?

Juan Bermejo Vega

La función booleana AND no se puede calcular. Supongamos que la función AND se calcula mediante un circuito . Luego se deduce que uno de los subcircuitos MOD debe calcular entonces Y funcionar ya, lo cual es imposible. $\text{OR} \circ \text{MOD}$

Kristoffer Arnsfelt Hansen
fuente

No, él tiene razón. La suposición implícita aquí es que n es constante y deberíamos poder manejar un número arbitrariamente grande de entradas con puertas mod_n.

Gadi A

@GadiA Ah, está bien. Esto no estaba claro en su pregunta, al menos para las personas que no están familiarizadas con el campo. Hice una edición menor que debería aclarar esto.

Gilles 'SO- deja de ser malvado'

Sí, mi pregunta estaba muy mal redactada, lo siento.

Gadi A

@Gilles ¿Puedes explicarme qué fanáticos consideramos aquí? El problema para mí es que no puedo ver por qué el subcircuito de MOD no puede calcular AND. ¿Cuántas entradas tiene este MOD y este AND?

¿Los circuitos de profundidad 2 con compuertas OR y MOD no son universales?

Respuestas: