Temos algum circuito uniforme não trivial?

Dado um algoritmo em execução no tempo , podemos convertê-lo em uma família de circuitos uniformes "triviais" para o mesmo problema de tamanho, no máximo .$t(n)$$\approx t(n)\log t(n)$

Por outro lado, pode ser que tenhamos circuitos uniformes muito menores para esse problema, mesmo que seja um tempo de execução ideal. Os circuitos podem demorar mais que para gerar, mas são pequenos.t ( n $t(n)$$t(n)$

Mas nós realmente sabemos como construir essas coisas? Eu acho que a pergunta inicial a fazer é

(1) Temos exemplos construtivos de circuitos uniformes não triviais, ou seja , circuitos uniformes cujo tamanho é menor que o tempo de execução mais conhecido de qualquer algoritmo para o mesmo problema?

Agora, acredito que, se houver um problema em , teremos um algoritmo de tempo exponencial para encontrar circuitos ideais usando uma pesquisa exaustiva: Dado , escrevemos as respostas em todos os entradas (tendo tempo ); então enumeramos todos os circuitos em entradas em tamanho crescente até encontrar um que dê todas as respostas corretas. A pesquisa termina no tamanho da conversão trivial, ou na tabela verdade da função, se as saídas forem . (Editar: Thomas ressalta que o limite é devido a Shannon / Lupanov.) n 2 n ( 2 n ) t ( n ) n t ( n ) log t ( n ) 2 n { 0 , 1 } O ( 2 n / n $\mathsf{DTIME(t(n))}$$n$$2^n$$(2^n)t(n)$$n$$t(n) \log t(n)$$2^n$$\{0,1\}$$O(2^n/n)$

Portanto, temos um "sim" insatisfatório para a pergunta (1): adote uma linguagem difícil por um tempo acima de , mas ainda decidível; o procedimento acima gera uma tabela verdade de tamanho .2 $2^n$$2^n$

Portanto, devemos refinar a pergunta (1). Eu acho que os dois casos mais interessantes são

(2) Temos exemplos construtivos de circuitos uniformes não triviais de tamanho polinomial ? (Mesmo que sejam gerados por algoritmos muito lentos.)

(3) Temos exemplos construtivos de circuitos uniformes não triviais, geráveis ​​em tempo polinomial e de tamanho polinomial?

Isso pode ser pedir demais. Que tal uma pergunta mais fácil: sabemos mesmo que isso é possível? Talvez não existam circuitos uniformes não triviais?

(4) A declaração a seguir é falsa para qualquer ? (Edit: , obrigado Thomas.) "Se uma linguagem possui circuitos uniformes do tamanho , também possui algoritmos em execução no tempo ". (Se sim, e quando "uniforme" é substituído por "polinomial-tempo-uniforme", "logspace uniform", etc?)O ( 2 n / n ) L O ( s ( n ) ) ~ O ( s ( n ) $s(n) = o(2^n)$$o(2^n/n)$$L$$O(s(n))$$\tilde{O}(s(n))$

Por fim, se as perguntas acima forem muito difíceis,

(5) Temos alguma construção de famílias uniformes de circuitos que não sejam simplesmente conversões de algoritmos em circuitos (ou anotando a tabela da verdade)?

Postscript. Um especialista que eu perguntei sobre isso mencionou "Sobre limites mais baixos de uniformidade e circuito" ( pdf ), Santhanam e Williams 2013, que talvez seja o trabalho mais estreitamente relacionado, mas prova limites mais baixos (que os circuitos geráveis ​​por tempo poli não são muito poderoso). Eu estaria interessado em qualquer outro trabalho relacionado!

Aqui estão as respostas para suas duas últimas perguntas.

(5) As redes de classificação são circuitos uniformes que classificam tão rapidamente quanto os melhores algoritmos de RAM, mas definitivamente não são apenas conversões de algoritmos de RAM (por exemplo, quicksort). [ AKS83 , G14 ]

$s(n)=(1+\varepsilon) \cdot 2^n/n$$\varepsilon>0$$(1+o(1)) \cdot 2^n/n$$f$$\Omega(3^n)$$O(n \cdot 3^n)$$f$$O(2^n/n)$$2^{\mathrm{poly}(n)}$$\tilde{O}(2^n/n)$$s(n) = o(2^n/n)$

Esta é uma pergunta interessante; Espero que alguém possa responder (1) - (3).