Implicações do limite inferior do circuito

7

Há um resultado básico na complexidade do circuito que diz:

Existe uma linguagem que não pode ser resolvida com circuitos do tamanho .o(2nn)

O argumento é um argumento simples de contagem do número de funções booleanas e do número de circuitos distintos. Veja, por exemplo, estas notas de aula .

Acredito que não se sabe se esse limite é ou não apertado. Ou seja, não sabemos se a seguinte declaração é verdadeira:

Todo idioma pode ser resolvido com circuitos do tamanho .O(2nn)

Se essa afirmação fosse verdadeira, teria implicações interessantes para a teoria da complexidade?

GMB
fonte

Respostas:

7

Isso foi comprovado por Muller já em 1956. Aqui está a construção. Seja um parâmetro. Primeiro calculamos todas as funções possíveis nas primeiras entradas no tamanho (veja abaixo). Em seguida, construímos uma árvore de decisão para as outras variáveis , conectando-a à função correta nas variáveis ​​restantes. Isso leva (veja abaixo), para um total de . Escolhendo , obtemos o limite desejado.kkO(22k)nkO(2nk)O(22k)+O(2nk)k=log(nlogn)

Calculamos todas as funções possíveis em entradas indutivamente. Seja o tamanho de um circuito que computa todas as funções possíveis em entradas. Existem duas funções nas entradas zero, então . Toda função nas entradas pode ser escrita como , então . A solução dessa recorrência é .kZkkZ0=2f(x1,,xk)kxkf(x1,,xk1,1)+xk¯f(x1,,xk1,0)Zk=Zk1+22kO(1)Zk=O(22k)

Para calcular a árvore de decisão, usamos uma construção semelhante: dada uma árvore para os primeiros variáveis, podemos construir uma árvore para os primeiros variáveis do formulário . A recorrência que obtemos é , cuja solução é .Tk1kxkT+xk¯TWk=2Wk1+O(1)Wk=O(2k)

Yuval Filmus
fonte
Entendi a construção da árvore de decisão e do circuito computando todas as saídas possíveis, mas não conseguia entender como combiná-las produz um circuito para . Você se importaria de elaborar isso um pouco mais? f
precisa
Veja o Teorema 1.5 aqui: people.csail.mit.edu/rrw/cs294-2018/hardest-fns.pdf .
Yuval Filmus 22/10