Teorema da hierarquia para o tamanho do circuito

18

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)nO(1)

Existe um resultado nessa direção?

AntonioFa
fonte

Respostas:

31

De fato, é possível mostrar que, para cada f suficientemente pequeno (inferior a 2n/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 ) .g2n/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.zz(x)=0x
  3. se duas funções e g 2 diferem apenas em uma entrada, sua complexidade do circuito difere em no máximo O ( n )g1g2O(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 .gNx1,,xNigi(x){x1,,xi}g0=0gN=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 ) .igi+1f(n)gif(n)gif(n)f(n)O(n)

Luca Trevisan
fonte
3
Como é a prova de que existem funções computáveis ​​pelos circuitos do tamanho mas não pelos circuitos do tamanho f ( n ) - O ( 1 ) ? f(n)f(n)O(1)
William Hoza
28

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 gk(1+o(1))(2k/k)k2g(n)<2k/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)k2n/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

Russell Impagliazzo
fonte
6
Não há razão direta, mas todas as abordagens conhecidas (implementações de argumentos de contagem) exigem que verifiquemos se a tabela verdade de uma determinada função possui alta complexidade de circuitos. Um algoritmo para este problema seria definir um N P / p o l y propriedade -natural contra P / p o l y (que, de acordo com um dos documentos de Steven Rudich, é pouco provável). Claro, a solução deste problema parece desnecessário ...NENP/polyP/poly
Ryan Williams