Numero inferiore del numero di (diversi) circuiti delle dimensioni specifiche?

Question

Per i circuiti con $ N $ bit di ingresso, lo sappiamo, per qualsiasi funzione $ s $ , ci sono al massimo $ o (s (n) ^ {s (n)})= o (2 ^ {s (n) \ log s (n)}) $ < / SPAN> Circuiti con dimensioni al massimo $ s (n) $ .

Dì due circuiti $ c_1 $ e $ c_2 $ sono diversi Se la funzione che calcola è diversa, cioè, c'è una $ N $ -bit stringa $ x $ tale che $ c_1 (x) \ neq c_2 (x) $ . La classe $ o (s (n) ^ {s (n)}) $ legato sopra è un legato sul numero di circuiti di una determinata dimensione. C'è un noto il limite inferiore sul numero di circuiti diversi con dimensioni al massimo $ s (n) $ per diversi valori di $ s (n) $ (ad esempio, $ s (n) \ in \ mathsf {poly} (n) $ , $ s (n) \ in n ^ {\ textsf {poliylog} (n)} $ o $ s ( n)= 2 ^ {n ^ \ varepsilon} $ )?

chiaramente un tale rilegato deve essere strettamente più piccolo della $ o (s (n) ^ {s (n)}) $ rilegato poiché ci sono coppie di circuiti Con diverse strutture (e anche diversi numeri di cancelli) e che comunicano tuttavia la stessa funzione (cioè, non sono "diversi" come definiti sopra) - ma quanto può essere più piccolo?

Answer 1

Let $ 1000 \ Leq S \ Leq 2 ^ N / N $ . Ogni funzione su $ m $ bit può essere calcolato da un circuito di dimensioni $ o (2 ^ m / m) $ (credo che sia nota anche la costante ottimale).Scegli un valore di $ M $ In tal modo che ogni funzione su $ m $ bit può essere calcolato da un circuitodi taglia $ s $ e inoltre $ s=omega (2 ^ m / m) $ . Dal momento che ci sono $ 2 ^ {2 ^ m}= s ^ {\ ^ m}= s ^ {\ omega (s)} $ diverse funzioni su $ m$ bit, vediamo che il tuo limite superiore è abbastanza stretto.