Baje el límite en el número de circuitos (diferentes) de tamaño dado?

Question

para circuitos con $ n $ bits de entrada, sabemos que, para cualquier función $ s $ , hay como máximo $ O (s (n) ^ {s (n)})= O (2 ^ {s (n) \ log s (n)}) $ < / SPAN> CIRCUITOS CON TAMAÑO A LA MÁS $ S (N) $ .

DIGA DOS CIRCUITOS $ C_1 $ y $ c_2 $ son diferentes Si la función que calculan es diferente, es decir, hay un $ n $ -bit string $ x $ tal que $ c_1 (x) \ neq c_2 (x) $ . El $ O (s (n) ^ {s (n)}) $ unido arriba es un límite superior en el número de circuitos de un tamaño dado. ¿Hay un límite inferior conocido en el número de circuitos diferentes con el tamaño en la mayoría de los $ s (n) $ para diferentes valores de $ s (n) $ (por ejemplo, $ s (n) \ in \ mathsf {poly} (n) $ , $ s (n) \ in n ^ {\ textsf {polylog} (n)} $ , o $ s ( n)= 2 ^ {n ^ \ varepsilon} $ )?

Claramente, un límite de este tipo debe ser estrictamente más pequeño que el $ O (s (n) ^ {s (n)}) $ unido ya que hay pares de circuitos con diferentes estructuras (e incluso un número diferente de puertas) y, que, sin embargo, calculan la misma función (es decir, no son "diferentes" como se define anteriormente): ¿Pero cuánto más pequeño puede ser?

Answer 1

Let $ 1000 \ leq s \ leq 2 ^ n / n $ . Cada función en $ m $ bits se puede calcular por un circuito de tamaño $ o (2 ^ m / m) $ (Creo que incluso la constante óptima es conocida).Elija un valor de $ m $ de modo que cada función en $ m $ bits se puede calcular por un circuitode tamaño $ s $ , y además $ s=omega (2 ^ m / m) $ . Dado que hay $ 2 ^ {2 ^ m}= s ^ {\ onga (s)} $ diferentes funciones en $ m$ bits, vemos que su límite superior está bastante ajustado.