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

É 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(n-1)$

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

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 ⌊ $n=3$$5$$\lfloor \frac 52 n \rfloor-2$$n$

É 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).

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.$n\ge2$$2n-1$

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.$3$$n=2$$C$$n>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.$x_i$$0$

Seja portão de nível inferior no circuito. Sem perda de generalidade, a = x 1 ∧ x 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 2 ∧ c 1 ∧ ⋯ ∧ c r . Observe que em$a$$a=x_1\land x_2\land\cdots$$x_1=0$$a=0$$C'$$x_2$$x_2$$b=\neg x_2\land c_1\land\dots\land c_r$$C'$$c_j$$x_2$$x_3,\dots,x_n$$x_1=0$$c_j$$x_2$$\neg x_2$$C'$$c_j$$1$$b$ , portanto, podemos eliminá-lo junto com a .$\neg x_2$$a$

EDIT: Como aprendi no artigo de Yuri Kombarov, este limite inferior , bem como o ⌊ $2n-1$limite superior implícito na resposta de Marzio De Biasi, foram originalmente provados em$\lfloor\frac52n\rfloor-2$

[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

Amplio meu comentário:

$k$$k-1$$I_i \geq 2$$g_i$

$3(n-1)$$(x_1,x_2,x_3)$

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