Baixa inferior no número de circuitos (diferentes) de determinado tamanho?

Question

Para circuitos com $ n $ bits de entrada, sabemos que, para qualquer função $ S $ , há no máximo $ o (s (n) ^ {s (n)})= O (2 ^ \ {S (n) \ log s (n)}) $ < / span> circuitos com tamanho no máximo $ s (n) $ .

Diga dois circuitos $ c_1 $ e $ c_2 $ são diferentes Se a função que eles computarem é diferente, isto é, há uma $ n $ -bit string $ x $ De tal modo que $ c_1 (x) \ neq c_2 (x) $ . A $ o (s (n) ^ {s (n)}) $ ligado acima é um limite superior sobre o número de circuitos de um determinado tamanho. Existe um vinculado mais baixo no número de diferentes circuitos com tamanho no máximo $ s (n) $ para diferentes valores de $ s (n) $ (por exemplo, $ s (n) \ in \ mathsf {poly} (n) $ , $ s (n) \ in n ^ {\ textsf {polylog} (n)} $ , ou $ s ( n)= 2 ^ {n ^ \ varepsilon} $ )?

Claramente tão ligado deve ser estritamente menor do que a $ o (s (n) ^ {s (n)}) $ limite desde que existem pares de circuitos com estruturas diferentes (e mesmo número diferente de portões) e que, no entanto, computa a mesma função (ou seja, eles não são "diferentes" como definidos acima) - Mas quão menor pode ser?

Answer 1

Deixe $ 1000 \ LEQ S \ LEQ 2 ^ N / N $ . Cada função em $ m $ bits pode ser calculado por um circuito de tamanho $ O (2 ^ m / m) $ (Acredito que até mesmo a constante ideal é conhecida).Escolha um valor de $ m $ tal que cada função na $ m $ bits pode ser calculado por um circuitode tamanho $ s $ , e além disso $ s= ímã (2 ^ m / m) $ . Como há $ 2 ^ ^ {2 ^ m}= s ^ {\ Ômega (s)} $ diferentes funções na $ m$ bits, vemos que o limite superior é bastante apertado.