PARIDADE

$AC^0$ é a classe de circuitos de tamanho polinomial de profundidade constante com portas NOT e portas AND e OR sem ventoinha, em que entradas e portas também possuem saída fanout ilimitada.

Agora considere uma nova classe, chame-a de que é como mas para quais entradas e portões têm fanout no máximo . Esta classe está claramente em . De fato, está estritamente contido em , como observado aqui . Portanto, PARITY obviamente não está em . $AC^0_{bf}$ $AC^0$ $O(1)$ $AC^0$ $AC^0$ $AC^0_{bf}$

Existe uma prova de PARIDADE que também não passa por ? Em outras palavras, existe uma prova que não use técnicas poderosas como o lema da troca ou o método Razborov / Smolensky? $\notin AC^0_{bf}$ $AC^0$

cc.complexity-theory circuit-complexity Adam Paetznick
fonte

Isso é chamado de na literatura: qwiki.stanford.edu/index.php/Complexity_Zoo:N#nc0

{N C}^{0}

$\mathsf{NC}^0$

Hsien-Chih Chang張顯之

Não, não é, pois o fanin é ilimitado.

21411 domotorp

Ah, eu interpretei mal a palavra fanout. Obrigado por apontar.

Hsien-Chih Chang #: 19/07/11

Artigo relacionado por @Kaveh: cstheory.stackexchange.com/q/1824/1800 , movido dos comentários abaixo para aumentar a exposição.

Hsien-Chih Chang # 21/07

O que é 'fanout limitado', a propósito?

xxx ---

Respostas:

Eu posso sentir falta de algo, mas o mesmo que uma fórmula? Como todo bit de entrada pode afetar no máximo um número limitado de portas, podemos simplesmente supor que cada porta tenha apenas uma saída (depois de possivelmente duplicar algumas coisas) e também podemos empurrar as portas para baixo. Sabemos que o tamanho da fórmula da paridade é n ^ 2 (veja Troy J. Lee, " O tamanho da fórmula da PARIDADE ", 2007) e, como em todos os níveis do nosso circuito só podemos ter O (n) portas, isso mostra que paridade não está em . $AC^0_{bf}$ $AC^0_{bf}$

domotorp
fonte

então com "Formula" você quer dizer fórmula de tamanho linear, certo? e por tamanho você quer dizer o tamanho da fórmula ...

Alessandro Cosentino

Acho que sua resposta está correta no final, mas o raciocínio é mais sutil. A fanout do gate pode ser reduzida duplicando partes do circuito, mas isso aumenta o tamanho da fórmula. (O tamanho da fórmula é equivalente ao número de fios de entrada.) Digamos que o fanout do portão seja no máximo 2. Em seguida, para reduzir o fanout dos portões da camada inferior, preciso duplicar cada gate e cada entrada, duplicando o tamanho da fórmula. Repetir esse processo para cada camada gera uma fórmula de tamanho que é a profundidade do circuito. No nosso caso, é uma constante, portanto o tamanho da fórmula ainda é linear.

O (2^{d} n)

$O(2^dn)$

d

$d$

d

$d$

Adam Paetznick

Foi exatamente isso que eu quis dizer, desculpe se minha exposição foi ruim.

21411 Domotorp

@ Alessandro: Me desculpe se não entendi sua pergunta. Mas minha primeira impressão é que é possível transformar qualquer circuito de profundidade d do tamanho em uma fórmula de profundidade d (fanout 1) de tamanho sobre : basta ir camada por camada começando de baixo (ao lado das entradas) ) camada e tire várias cópias do mesmo portão; em cada camada o número de portas pode aumentar por, no máximo, o factor de . Isso significa que qualquer limite inferior para fórmulas implica um limite inferior $S$ $S^d$ $S$ $S$ $AC^0$ $S^{1/d}$ $AC^0$ $AC^0$ $AC^0$ $d$

$X$ $1$ $n$

Stasys
fonte

S^{d}

$S^d$

k^{d} S

$k^dS$

k

$k$

S

$S$

A C_{b f}^{0}

$AC^0_{bf}$

A C^{0}

$AC^0$

k n

$kn$

k^{2} n

$k^2n$

O (n)

$O(n)$

A C^{0}

$AC^0$

A C_{b f}^{0}

$AC^0_{bf}$

Alguém pode me dizer por que esse modelo "não mais que k cópias de uma variável de entrada" é interessante? Mesmo quando a profundidade é constante. Em que contexto surge esse modelo? Estou apenas curioso.

Stasys 21/07

Q A C^{0}

$QAC^0$

A C^{0}

$AC^0$

n \log n

$n\log n$