Límite superior de complejidad de los circuitos de fórmulas booleanas más difíciles

Question

Me he topado con el resultado de Shannon que establece que el número máximo de puertas de un circuito necesarias para calcular una función booleana en n bits, $f:\{0,1\}^n \to \{0,1\}$ es $\Theta (2^n/n)$ .

Hasta ahora he podido demostrar que el número de puertas necesario está comprendido entre $\Omega(2^n/n)$ y $O(2^n)$ pero necesito un límite superior mejor.

El actual se demostró de la siguiente manera. Observamos que

$f(x_1,\dots, x_n) = (\neg x_n \wedge f(x_1,...,x_{n-1},0))\lor(x_n \wedge f(x_1,...,x_{n-1},1))$ $(1)$

por lo que debe ser que el número de circuitos necesarios para calcular la función más difícil en n bits, $\lambda (n)$ es inferior a $5 + 2\lambda (n-1)$ . Una comprobación rápida muestra que entonces $\lambda(n) = O(2^n)$ .

He intentado un análisis similar para demostrar el límite más fuerte. Mi estrategia consistió en aplicar la expansión $(1)$ sólo para $n-log(n)$ niveles. Eso nos permite determinar que $\lambda(n) = O(2^{n-log(n)} + X)$ donde $X$ es el número de puertas necesarias para calcular el resto de $2^{n-k}$ funciones en $log(n)$ bits.

Si de alguna manera demostrara que $X = O(2^n/n)$ entonces tendría el resultado. Pero no se me ocurre cómo hacerlo.

Answer 1

Resulta que, en realidad, la pregunta era fácil de responder.

Consideremos un circuito mínimo de $2^{n}/n$ puertas con $log(n)$ es decir, no hay dos nodos del circuito que calculen la misma función. Esto es factible, ya que no estamos limitados por el abanico. Entonces es lógico que cada función en $log(n)$ bits es calculado por algún nodo, que podemos utilizar para obtener la respuesta que necesitamos.

Así $X = 2^{n}/n$ y el resultado se deduce tal y como razoné en la pregunta.