Qual é o tamanho mínimo de um circuito que calcula PARITY?

21

É um resultado clássico que todo circuito fan-in 2 AND-OR-NOT que calcula PARITY a partir das variáveis ​​de entrada tem tamanho pelo menos e isso é nítido. (Definimos tamanho como o número de portas AND e OR.) A prova é por eliminação de porta e parece falhar se permitirmos fan-in arbitrário. O que é conhecido para este caso?3(n1)

Especificamente, alguém conhece um exemplo quando um fan-in maior ajuda, ou seja, precisamos de menos de portões?3(n1)

Atualização em 18 de outubro. Marzio mostrou que para até portas são suficientes usando o formulário CNF de PARITY. Isto implica um limite de para o geral . Você pode fazer melhor?5 5n=35n52n2n

domotorp
fonte
Este artigo pode estar relacionado. A base, no entanto, aqui é muito maior que AND, OR.
Stasys
A resposta a seguir está (remotamente) relacionada à sua pergunta. cstheory.stackexchange.com/questions/3624/…
Hermann Gruber
11
Nos limites superiores e , na verdade você está ignorando as negações em todos os lugares, e não apenas nas variáveis, certo? 53n52n
Emil Jeřábek apoia Monica
11
Como você faz isso sem duplicar o portão, caso ele seja usado tanto positiva quanto negativamente?
Emil Jeřábek apoia Monica
11
@ Harry: Você precisa de k-1 fan-in gates, mas eles podem ser colocados em profundidade . Esta pergunta é sobre SIZE e não PROFUNDIDADE! logk
Domotorp # 21/14

Respostas:

10

É possível calcular a paridade usando apenas portas 2.33n + C. A construção é bastante simples e é apresentada neste artigo.

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

Aqui está um exemplo de um circuito para paridade de 6 variáveis ​​usando apenas 12 portas (cada porta é uma porta AND, um círculo perto da entrada de uma porta significa que essa entrada é invertida). Note que um circuito para paridade de 6 variáveis ​​que é construído empilhando blocos DNF (como no limite superior de Marzio) consiste em 13 portas.

Eu verifiquei que para n = 2,3,4,5,6 os tamanhos de circuitos ideais são 3,5,8,10,12. Esses valores também são tamanhos de circuitos que dão 2,33n limite superior. Ainda não sei se 2.33n é o tamanho do circuito ideal para cada n. Ainda mais, não sei o tamanho do circuito ideal para paridade de 7 variáveis ​​(existem dois valores possíveis, 14 e 15). Circuito para patidade de 6 variáveis

Yuri Kombarov
fonte
10

Esse limite inferior de eliminação de porta não corresponde ao limite superior de Marzio, mas é um começo.

Proposição: Toda paridade de computação de circuito AND / OR / NOT fan-ilimitado em variáveis ​​contém pelo menos 2 n - 1 portas AND e OR.n22n1

Por conveniência, usarei um modelo em que os únicos portões são AND-port, mas permitimos fios de negação. É fácil ver que portas são necessárias para n = 2 , portanto é suficiente mostrar que se C é uma paridade de computação de circuito de tamanho mínimo em n > 2 variáveis, podemos encontrar uma restrição de uma variável que mata pelo menos dois portões.3n=2Cn>2

Se alguma variável tiver pelo menos dois pais positivos (ou seja, for conectada por fios não -egegados a dois portões diferentes), definir essa variável como 0 matará os pais e nós terminamos; da mesma forma, se tiver dois pais negativos. Assim, podemos assumir que cada variável tem no máximo um pai positivo e no máximo um pai negativo.xi0

Seja portão de nível inferior no circuito. Sem perda de generalidade, a = x 1x 2 . Defina x 1 = 0 , o que força a = 0 e mata-o. O circuito restrito C ' ainda calcula paridade, em particular, depende de X 2 , por conseguinte, x 2 tem um pai negativo b = ¬ x 2c 1c r . Observe que emaa=x1x2x1=0a=0Cx2x2b=¬x2c1crCcjx2x3,,xnx1=0cjx2¬x2Ccj1b , portanto, podemos eliminá-lo junto com a .¬x2a

EDIT: Como aprendi no artigo de Yuri Kombarov, este limite inferior , bem como o 52n1limite superior implícito na resposta de Marzio De Biasi, foram originalmente provados em52n2

[1] Ingo Wegener, A complexidade da função de paridade em circuitos de profundidade ilimitados, com fan-in , Theoretical Computer Science 85 (1991), n. 1, pp. 155-170. http://dx.doi.org/10.1016/0304-3975(91)90052-4

Emil Jeřábek apoia Monica
fonte
Sim, então a questão é se podemos eliminar 5 portas, consertando 2 variáveis.
Domotorp 19/10/2014
Direita. Ou melhor ainda, se pudermos eliminar 3 portas, fixando uma variável quando for par. n
Emil Jeřábek apoia Monica
8

Amplio meu comentário:

kk1Ii2gi

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

3(n1)(x1,x2,x3)

insira a descrição da imagem aqui

Marzio De Biasi
fonte
Bom, na verdade para n = 3, a CNF tem apenas 5 portas! Gostaria de saber se alguém pode fazer ainda melhor em geral.
Domotorp 18/10/2014
Eu não pensei muito sobre isso, mas certamente você pode combinar e usar em paralelo o circuito acima e obter, por exemplo, um circuito PARITY para 9 variáveis ​​que usa apenas 20 portas em vez de 24
Marzio De Biasi
Eu fiz e atualizei minha pergunta.
Domotorp 19/10/2014
2

5n/2

Se houver um literal com 3 pais, podemos eliminar todos os 3 com uma variável.

Se dois literais ocorrem juntos em 2 portas diferentes, juntos, podemos aplicar o argumento principal da resposta de Emil, eliminando novamente 3 portas com uma variável.

domotorp
fonte