¿Tenemos algún circuito uniforme no trivial?

Dado un algoritmo que se ejecuta en el tiempo , podemos convertirlo en una familia de circuitos uniforme "trivial" para el mismo problema de tamaño como máximo ≈ t ( n ) log t ( n ) .$t(n)$$\approx t(n)\log t(n)$

Por otro lado, podría ser que tengamos circuitos uniformes mucho más pequeños para ese problema, incluso si es un tiempo de funcionamiento óptimo. Los circuitos pueden tardar más de t ( n ) en generarse, pero son pequeños.$t(n)$$t(n)$

Pero, ¿sabemos realmente cómo construir tales cosas? Creo que la pregunta inicial es

(1) ¿Tenemos ejemplos constructivos de circuitos uniformes no triviales, es decir , circuitos uniformes cuyo tamaño es menor que el tiempo de ejecución más conocido de cualquier algoritmo para el mismo problema?

Ahora, creo que si hay un problema en , entonces tenemos un algoritmo de tiempo exponencial para encontrar circuitos óptimos usando una búsqueda exhaustiva: dado n , escribimos las respuestas en los 2 n entradas (toma tiempo ( 2 n ) t ( n ) ); luego enumeramos todos los circuitos en n entradas en tamaño creciente hasta que se encuentre uno que dé todas las respuestas correctas. La búsqueda termina en el tamaño de la conversión trivial, t ( n ) $\mathsf{DTIME(t(n))}$$n$$2^n$$(2^n)t(n)$$n$ , o la tabla de verdad de la función, 2 n si las salidas son { 0 , 1 } . (Editar: Thomas señala que el límite es O ( 2 n / n ) debido a Shannon / Lupanov).$t(n) \log t(n)$$2^n$$\{0,1\}$$O(2^n/n)$

Entonces, tenemos un "sí" insatisfactorio a la pregunta (1): tome un lenguaje que sea difícil por más de , pero que todavía sea decidible; el procedimiento anterior genera una tabla de verdad de tamaño 2 n .$2^n$$2^n$

Entonces debemos refinar la pregunta (1). Creo que los dos casos más interesantes son

(2) ¿Tenemos algún ejemplo constructivo de circuitos uniformes no triviales de tamaño polinómico ? (Incluso si son generados por algoritmos muy lentos).

(3) ¿Tenemos algún ejemplo constructivo de circuitos uniformes no triviales de tamaño polinómico generables en tiempo polinómico?

Esto puede ser demasiado pedir. ¿Qué tal una pregunta más fácil: ¿Sabemos siquiera que tal cosa es posible? ¿Quizás no existen circuitos uniformes no triviales?

(4) ¿Se sabe que la siguiente declaración es falsa para cualquier ? (Editar: o ( 2 n / n ) , gracias Thomas.) "Si un lenguaje L tiene circuitos uniformes de tamaño O ( s ( n ) ) , también tiene algoritmos que se ejecutan en el tiempo ˜ O ( s ( n ) ) . " (Si es así, ¿qué sucede cuando "uniforme" se reemplaza por "uniforme de tiempo polinómico", "uniforme de espacio de registro", etc.?)$s(n) = o(2^n)$$o(2^n/n)$$L$$O(s(n))$$\tilde{O}(s(n))$

Finalmente, si las preguntas anteriores son demasiado difíciles,

(5) ¿Tenemos alguna construcción de familias uniformes de circuitos que no sean simplemente conversiones de algoritmos en circuitos (o que anoten la tabla de verdad)?

Posdata. Un experto al que le pregunté sobre esto mencionó "Sobre uniformidad media y límites inferiores del circuito" ( pdf ), Santhanam y Williams 2013, que tal vez sea el trabajo más relacionado, pero demuestra los límites inferiores (que los circuitos de tiempo polivinílico no son demasiado poderoso) ¡Me interesaría cualquier otro trabajo relacionado!

Aquí hay respuestas a sus últimas dos preguntas.

(5) Las redes de clasificación son circuitos uniformes que se clasifican tan rápido como los mejores algoritmos de RAM, pero definitivamente no son solo conversiones de algoritmos de RAM (por ejemplo, clasificación rápida). [ 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 es una pregunta interesante; Espero que alguien pueda responder (1) - (3).