¿Cuál es el tamaño mínimo de un circuito que calcula PARIDAD?

21

Es un resultado clásico que cada circuito 2-Y-O-NO de ventilador que calcula PARIDAD a partir de las variables de entrada tiene un tamaño de al menos y esto es nítido. (Definimos el tamaño como el número de compuertas AND y OR). La prueba es por eliminación de compuerta y parece fallar si permitimos un abanico arbitrario. ¿Qué se sabe para este caso?3(n1)

Específicamente, ¿alguien conoce un ejemplo cuando un fan-in más grande ayuda, es decir, necesitamos menos de puertas?3(n1)

Actualización 18 de octubre. Marzio ha demostrado que para incluso 5 puertas son suficientes utilizando la forma CNF de PARIDAD. Esto implica un límite de 5n=35parangeneral. ¿Puedes hacerlo mejor?52n2n

domotorp
fuente
Este documento puede estar relacionado. La base, sin embargo, aquí es mucho más grande que AND, OR.
Stasys
La siguiente respuesta está (remotamente) relacionada con su pregunta. cstheory.stackexchange.com/questions/3624/…
Hermann Gruber
1
Tanto en el como en el 53nlímites superiores, en realidad estás ignorando las negaciones entodas partes enlugar de solo en las variables, ¿verdad? 52n
Emil Jeřábek apoya a Monica el
1
¿Cómo se hace sin duplicar la puerta en caso de que se use tanto positiva como negativamente?
Emil Jeřábek apoya a Monica el
1
@Harry: Necesitas puertas de abanico k-1, pero se pueden colocar en el profundidad k . ¡Esta pregunta es sobre TAMAÑO y no PROFUNDIDAD! logk
domotorp

Respuestas:

10

Es posible calcular la paridad usando solo 2.33n + C puertas. La construcción es bastante simple y se da en este artículo.

http://link.springer.com/article/10.3103/S0027132215050083

Aquí hay un ejemplo de un circuito para la paridad de 6 variables usando solo 12 puertas (cada puerta es una puerta AND, un círculo cerca de la entrada de una puerta significa que esta entrada está invertida). Tenga en cuenta que un circuito para la paridad de 6 variables que se construye apilando bloques DNF (como en el límite superior de Marzio) consta de 13 puertas.

He comprobado que para n = 2,3,4,5,6 los tamaños de los circuitos óptimos son 3,5,8,10,12. Estos valores también son tamaños de circuitos que dan un límite superior de 2.33n. Todavía no sé si 2.33n es el tamaño del circuito óptimo para cada n. Aún más, no sé el tamaño del circuito óptimo para la paridad de 7 variables (hay dos valores posibles, 14 y 15). Circuito para la patidad de 6 variables.

Yuri Kombarov
fuente
10

Este límite inferior de eliminación de puerta no coincide con el límite superior de Marzio, pero es un comienzo.

n22n1

3n=2Cn>2

xi0

aa=x1x2x1=0a=0Cx2x2b=¬x2c1crCcjx2x3,,xnx1=0cjx2¬x2Ccj1b¬x2a

2n152n2

[1] Ingo Wegener, La complejidad de la función de paridad en circuitos de profundidad sin límites, sin límites , Theoretical Computer Science 85 (1991), no. 1, págs. 155-170. http://dx.doi.org/10.1016/0304-3975(91)90052-4

Emil Jeřábek apoya a Monica
fuente
Sí, entonces la pregunta es si podemos eliminar 5 puertas arreglando 2 variables.
domotorp
n
8

Expando mi comentario:

kk1Ii2gi

|C|+i(Ii2)3(n1)

3(n1)(x1,x2,x3)

ingrese la descripción de la imagen aquí

Marzio De Biasi
fuente
¡Agradable, de hecho para n = 3, el CNF tiene solo 5 puertas! Me pregunto si uno puede hacerlo aún mejor en general.
domotorp
No lo pensé demasiado, pero seguramente puedes combinar y usar en paralelo el circuito anterior y obtener, por ejemplo, un circuito PARITY para 9 variables que usa solo 20 puertas en lugar de 24
Marzio De Biasi
Lo hice y actualicé mi pregunta.
domotorp
2

5n/2

Si hay un literal con 3 padres, podemos eliminar los 3 con una variable.

Si dos literales ocurren juntos en 2 puertas diferentes, juntos, podemos aplicar el argumento principal de la respuesta de Emil, eliminando nuevamente 3 puertas con una variable.

domotorp
fuente