É

Na pesquisa "Circuitos Quânticos de Profundidade Pequena" de D. Bera, F. Green e S. Homer (p. 36 da ACM SIGACT News, junho de 2007 vol. 38, n. 2) , li a seguinte frase:

A versão clássica de (na qual as portas e têm fanout no máximo constante) é comprovadamente mais fraca que .$QAC^0$$AND$$OR$$AC^0$

Uma referência para esta reivindicação está ausente. Vou chamar essa classe de , em que significa "fanout limitado". (O Zoológico da Complexidade está desativado e não posso verificar se essa classe já tem um nome na literatura). Se assumirmos fanout ilimitado para os bits de entrada, esses circuitos parecerão equivalentes a fórmulas de profundidade constante até um aumento polinomial no tamanho, de modo que a reivindicação acima não faz sentido. Em vez disso, se assumirmos fanout limitado também para os bits de entrada, não consigo pensar em nenhum idioma que separa essa classe de . Um possível candidato pode ser o idioma , ou seja , o idioma das strings com apenas um 1. É fácil mostrar$AC^0_{bf}$$bf$$AC^0$$X := \{x | \mbox{weight}(x) = 1 \}$$X \in AC^{0}$ , mas não consegui provar que .$X \notin AC^{0}_{bf}$

As perguntas são:

É realmente mais fraca do que ? Se for, alguma ideia ou referência sobre como provar isso? E qual é a linguagem que separa essas duas classes? E o ?$AC^0_{bf}$$AC^0$$X$

Um limite na saída dos bits e portas de entrada tornará o tamanho do circuito linear. Seja um limite na abertura dos portões e entradas. É um DAG com grau máximo de saída limitado por ke caminho máximo de comprimento d . O número de fios disponíveis em cada nível pode aumentar k vezes, e o número de fios disponíveis no topo é k n ; portanto, o número total de fios no circuito é no máximo k n ∑ d i = 0 k i ≤ k d + 1 n que é O ( n ) .$k$$k$$d$$k$$kn$$kn \sum_{i=0}^d k^i \leq k^{d+1} n$$O(n)$

Qualquer função que exija tamanho super-linear separará a classe de funções com uma saída limitada (aplicada também aos bits de entrada) de A C 0 . aqui estão alguns exemplos:$\mathsf{AC^0}$$\mathsf{AC^0}$

1. [CR96]: Uma função que precisa de tamanho super-linear é a 1$\mathsf{AC^0}$ - seletor aproximado$\frac{1}{4}$. A - seletor aproximado é qualquer função cujo valor seja:$\frac{1}{4}$

   • sempre que o número de 1 s for no máximo$0$$1$ ,$\frac{n}{4}$
   • sempre que o número de 0 s for no máximo$1$$0$ ,$\frac{n}{4}$
   • pode ser ou 1 caso contrário.$0$$1$

2. [Ros08] mostra que a classe tem complexidade de funções A C 0 n Θ ( k ) ( n 2 bits de entrada são possíveis arestas de um gráfico com n vértices). Isso fornece um tamanho de linha super inferior para k > 2 .$k$$\mathsf{AC^0}$$n^{\Theta(k)}$$n^2$$n$$k\gt 2$

3. Provavelmente é possível generalizar o exemplo em 2 can para a existência de qualquer subestrutura induzida fixa não trivial (exigindo mais de um bit) em uma dada estrutura não ordenada, por exemplo:

   • existência de um caminho de comprimento 2 em um dado gráfico,
   • ,$\#_1(x)=2$

   uma vez que requerem um número super constante de portas, dependendo de um bit que não é possível em .$\mathsf{AC^0_{bf}}$

4. O exemplo mais fácil é um portão duplicador, ou seja, um portão que cria cópias do seu bit de entrada. Isso não é possível em A C 0 b f, pois apenas O ( 1 ) de portas pode depender de cada bit de entrada.$\omega(1)$$\mathsf{AC^0_{bf}}$$O(1)$

Além disso, qualquer circuito de tamanho S pode ser transformado em uma fórmula de tamanho no máximo k d S e, portanto, possui uma fórmula A C 0 b f de tamanho k 2 d + 1 n, de modo que qualquer função de A C 0 superlinear a complexidade da fórmula não estará em A C 0 b f .$\mathsf{AC^0_{bf}}$$S$$k^dS$$\mathsf{AC^0_{bf}}$$k^{2d+1}n$$\mathsf{AC^0}$$\mathsf{AC^0_{bf}}$

Referências:

[CR96] S. Chaudhuri e J. Radhakrishnan, " Restrições determinísticas na complexidade do circuito ", 1996

[Ros08] Benjamin Rossman, " Sobre a complexidade em profundidade constante do k-Clique ", 2008

[Juk] Stasys Jukna, " Complexidade da função booleana: avanços e fronteiras ", rascunho