Contagem de circuitos com restrições

Question

Por favor, perdoe-me se esta questão é trivial, eu não podia vir para cima com uma resposta (nem que encontrar um).

A fim de demonstrar que não são funções booleanas $f :\{0,1\}^n ightarrow \{0,1\}$ o que pode ser calculada usando apenas circuitos de tamanho $\Omega(2^n/n)$, usamos uma contagem argumento:há no máximo $O(2^{k \log k})$ circuitos de tamanho $k$, e $2^{2^n}$ tais funções.

Suponha que eu estou interessado na contagem de circuitos de tamanho $k$ que calcular diferentes funções.O "simples" contar argumento não funciona, pois pode ser possível que dois "sintaticamente" diferentes circuitos realmente computar a mesma função.Em outras palavras, eu quero vinculado o tamanho do conjunto: $$F = \{ f:\{0,1\}^n ightarrow \{0,1\} | f ext{ pode ser calculado usando-se um circuito de tamanho }k \} $$

Em seguida, $|F| < $ o número de circuitos de tamanho $k$ (uma vez que qualquer circuito calcula uma função), mas como eu obrigado $|F|$ a partir de baixo?(i.é. $ x <|F|$)

Answer 1

A fim de dependente o número de funções calculado por circuitos de tamanho $k$, você tem pelo menos duas opções de escolha:

• Construir um grande número de circuitos de tamanho $k$, que , pela construção de computação de funções diferentes.
• Considere um natural de distribuição de probabilidade em circuitos de tamanho $k$, e estimar a probabilidade de que dois circuitos aleatórios calcular a mesma função.

Como um exemplo, é sabido que cada função $m$ variáveis pode ser calculada por um circuito de tamanho $O(2^m/m)$.Considerando funções de forma $f_1(x_1,\ldots,x_m) \lor \cdots \lor f_{n/m}(x_{n-m+1},\ldots,x_n)$, isso mostra que há pelo menos $(2^{2^m})^{n/m}$ diferentes funções calculado por circuitos de tamanho $k = O(n2^m/m^2)$.Em termos de $k$, o número de funções é aproximadamente exponencial em $k\log k$, para $m \gg log n$.