Teorema da hierarquia para o tamanho do circuito

Penso que um teorema da hierarquia de tamanho para a complexidade do circuito pode ser um grande avanço na área.

É uma abordagem interessante para a separação de classes?

A motivação para a pergunta é que temos que dizer

existe alguma função que não pode ser calculada pelos circuitos de tamanho e pode ser calculada por um circuito de tamanho que . (e possivelmente algo sobre a profundidade)$f(n)$$g(n)$$f(n)<o(g(n))$

portanto, se , a propriedade parece não natural (ela viola a condição de grandeza). Claramente, não podemos usar a diagonalização, porque não estamos em uma configuração uniforme.$f(m)g(n) \leq n^{O(1)}$

Existe um resultado nessa direção?

De fato, é possível mostrar que, para cada $f$ suficientemente pequeno (inferior a $2^n/n$ ), existem funções computáveis ​​por circuitos de tamanho $f(n)$ mas não por circuitos de tamanho $f(n)-O(1)$ , ou até $f(n)-1$ , dependendo do tipo de porta que você permitir.

Aqui está um argumento simples que mostra que existem funções computáveis ​​no tamanho mas não no tamanho f ( n ) - O ( n ) .$f(n)$$f(n)-O(n)$

Nós sabemos isso:

1. existe uma função que requer complexidade do circuito pelo menos 2 n / O ( n ) e, em particular, complexidade do circuito mais que f ( n ) .$g$$2^n/O(n)$$f(n)$
2. a função tal que z ( x ) = 0 para cada entrada x é computável por um circuito de tamanho constante.$z$$z(x)=0$$x$
3. se duas funções e g 2 diferem apenas em uma entrada, sua complexidade do circuito difere em no máximo O ( n $g_1$$g_2$$O(n)$

Suponha que seja diferente de zero em N entradas. Chamar tais entradas x 1 , ... , x N . Podemos considerar, para cada i , a função g i ( x ), que é a função indicadora do conjunto { x 1 , … , x i } ; assim, g 0 = 0 e g N = g .$g$$N$$x_1,\ldots,x_N$$i$$g_i(x)$$\{ x_1,\ldots,x_i \}$$g_0=0$$g_N=g$

É evidente que há alguns tal que g de i + 1 tem complexidade de circuito mais do que f ( n ) e g i tem complexidade do circuito inferior a f ( n ) . Mas, em seguida, g i tem complexidade do circuito inferior a f ( n ) , mas mais do que f ( n ) - O ( n ) .$i$$g_{i+1}$$f(n)$$g_i$$f(n)$$g_{i}$$f(n)$$f(n) - O(n)$

Este resultado pode ser provado usando um simples argumento de contagem. Considere uma função aleatória aplicada aos primeiros bits da entrada. Essa função quase certamente tem complexidade de circuito ( 1 + o ( 1 ) ) ( 2 k / k ) pelo argumento de contagem de Riordan e Shannon e corresponde aos limites superiores. Assim, escolhendo k para que 2 g ( n ) < 2 k / k < f ( n ) / 2 possamos distinguir o tamanho $k$$(1+o(1))(2^k/k)$$k$$2g(n) < 2^k/k < f(n)/2$ do tamanho f ( n ) . Observe que as funções em questão nem sempre são computáveis, mas podemos colocá-las na hierarquia de tempo exponencial por técnicas padrão (desde que possamos calcular o valor correto de k ). É claro que não podemos provar um limite maior que 2 n / n , porque essa é a pior complexidade do circuito de qualquer função. $g(n)$$f(n)$$k$$2^n/n$

As provas naturais não se aplicam a esse tipo de argumento, porque a propriedade em questão é `` não ter um pequeno circuito '', que não é facilmente computável a partir da tabela verdade da função (presumivelmente). Não está claro o quão baixo em classes de complexidade esse tipo de contagem pode ocorrer. Existe alguma razão pela qual não podemos usar um argumento de contagem para provar limites mais baixos para ? Não que eu saiba. $NE$