Limites inferiores do tamanho da fórmula para funções AC0

25

Questão:

Qual é o limite inferior do tamanho da fórmula mais conhecido para uma função explícita no AC 0 ? Existe uma função explícita com um limite inferior Ω(n2) ?

Fundo:

Como a maioria dos limites inferiores, os limites inferiores do tamanho da fórmula são difíceis de encontrar. Estou interessado nos limites inferiores do tamanho da fórmula sobre o conjunto de portas universais padrão {AND, OR, NOT}.

O limite inferior do tamanho da fórmula mais conhecido para uma função explícita nesse conjunto de portas é para uma função definida por Andreev. Esse limite foi mostrado por Håstad, melhorando o limite inferior de Andreev . Outro limite inferior explícito é o limite inferior Khrapchenko para a função de paridade.Ω ( n 2,5 - o ( 1 ) ) Ω ( n 2 )Ω(n3o(1))Ω(n2.5o(1))Ω(n2)

No entanto, essas duas funções não estão no AC 0 . Gostaria de saber se sabemos uma função explícita no AC 0 com um limite inferior quadrático (ou melhor). O melhor limite que eu conheço é o limite inferior para a função Distinção de elemento, conforme mostrado por Nechiporuk. Observe que a função de distinção de elemento está no AC 0 , portanto, estou procurando um limite inferior para uma função explícita do AC 0 que seja melhor que , de preferência .Ω(n2/logn)Ω ( n 2 )Ω(n2/logn)Ω(n2)

Leitura adicional:

Um excelente recurso sobre o tema é "Complexidade da função booleana: avanços e fronteiras", de Stasys Jukna. Um rascunho do livro está disponível gratuitamente em seu site.

Robin Kothari
fonte
O motivo da falta de limites inferiores superlineares para funções ser algum tipo de auto-redutibilidade para funções A C 0 ? ou seja, se tivermos n 1 + ϵ limite inferior (onde ϵ não depende da profundidade), obteremos um limite inferior superpoli. AC0AC0n1+ϵϵ
precisa
@ Kaveh: Não sei se entendi. Já temos um limite inferior para uma função em A C 0 (distinção de elemento). Ω(n2/logn)AC0
Robin Kothari
Desculpe, substitua o superlinear por super-quadrático. Quero dizer algo semelhante ao resultado de Allender-Koucky para . O expoente para A C 0 pode ser maior. Resultado Tal pode explicar por que é difícil encontrar um C 0 lowerbounds para A C 0 funções. TC0AC0AC0AC0
precisa
Parece que qualquer problema que esteja completo para sob reduções de Turing N C 0 é fortemente auto-redutível, mas isso não parece dar o que eu esperava, uma vez que o tamanho da auto-redução pode ser polinomialmente grande. AC0NC0
Kaveh

Respostas:

15

Uma boa pergunta! Definitivamente, Khrapchenko não pode fornecer limites quadráticos inferiores para funções . Seu limite inferior é de fato pelo menos quadrado da sensibilidade média. E todas as funções em A C 0 têm sensibilidade média poli-logarítmica. Aparentemente, Subbotovskaya-Andreev também não pode fornecer essa função porque o argumento que eles usam (restrição aleatória resulta em fórmulas muito menores) é exatamente o motivo para forçar um tamanho de circuito A C 0 grande; O Lema Alternativo de Hastad (não tenho muita certeza, apenas uma intuição). A única esperança é Nechiporuk. Mas seu argumento não pode dar mais que n 2 / log nAC0AC0AC0n2/logn, por razões teóricas da informação. Então, pode ser que tudo em tenha fórmulas de tamanho quadrático (ou até menor)? Não acredito nisso, mas não consegui encontrar rapidamente um contra-exemplo. AC0

Na verdade, o fenômeno Allender-Koucky surge também em outro contexto - na complexidade gráfica. Digamos que um circuito de variáveis representa um bipartido n x n gráfico G em vértices V = { 1 , ... , 2 n } se para cada vector de entrada de um com exactamente dois 1s é, por exemplo, posições i e j ( i n , j > n ) o circuito aceita um vértices iff i e j2nn×nGV={1,,2n}aijinj>naijsão adjacentes em . Problema: exibem um gráfico explícito L requerendo, pelo menos, n £ portões de ser representado por uma monótona Σ 3 -circuit. Parece que uma pergunta inocente (uma vez que a maioria dos gráficos requerem cerca n 1 / 2 portões. Mas qualquer tais gráfico que nos dá uma função booleana de 2 m = 2 log n variáveis requerem não monótona circuitos de registo de profundidade de tamanho superlinear (por resultados de valente). Assim, mesmo provando n ε limites inferiores para a profundidade-3 circuitos pode ser um desafio. GGnϵ Σ3n1/22m=2lognnϵ

Stasys
fonte
Bem-vindo à história. :) (aliás, seus novo livro parece muito interessante, infelizmente eu não sou um falante nativo Inglês, portanto, não pode ajudar com leitura de prova-lo.)
Kaveh
Na verdade, quaisquer comentários / críticas sobre o conteúdo / referências, etc., também são muito importantes neste momento. A versão atual está aqui . Usuário: friend Senha: catchthecat
Stasys
Obrigado :) Vou ler os capítulos finais sobre a complexidade da prova proposicional.
Kaveh
2
Muito obrigado pela resposta! Se você pensa em uma função em que você conjectura requer uma fórmula do tamanho Ω ( n 2 ) , eu estarei interessado em saber. UMAC0 0Ω(n2)
Robin Kothari
12

Obrigado, Kaveh, por querer examinar os capítulos sobre a complexidade das provas!

Em relação à pergunta de Robin, primeiro a nota contém funções que requerem fórmulas (e até circuitos) de tamanho n k para qualquer constante k . Isso se segue, digamos, de um simples fato de que A C 0 contém todos os DNFs com monômios constantemente longos. Assim, A C 0 contém pelo menos exp ( n k ) funções distintas, para qualquer k . Por outro lado, temos no máximo funções exp ( t log n ) computáveis ​​por fórmulas de tamanho tAC0 nkkAC0AC0exp(nk)kexp(tlogn)t.

Em pouco tempo, discuti a questão de obter limites inferiores explícitos de ou maiores com Igor Sergeev (da Universidade de Moscou). Uma possibilidade poderia ser usar o método de Andreev, mas aplicado a outra função computável mais fácil, em vez de Parity. Ou seja, considere uma função de n variáveis ​​da forma F ( X ) = f ( g ( X 1 ) , , g ( X b ) ) em que b = log n e g é uma função em An2nF(X)=f(g(X1),,g(Xb))b=logng de n / b variáveis; f é uma função mais complexa dasvariáveis b (a mera existência de f é suficiente). Precisamos apenas que a função g não possa ser "eliminada" no seguinte sentido: se corrigirmos todas asvariáveis,exceto k , em X , será possível corrigir todas, exceto uma das variáveis ​​restantes de g, para que a subfunção obtida de g é uma única variável. Em seguida, aplicar o argumento de Andreev e usando o resultado de Hastad que a constante encolhimento é de pelo menos 2 (e não apenas 3 / 2AC0n/bfbfgkXgg23/2como mostrado anteriormente por Sybbotovskaya), o limite inferior resultante para será de cerca de n 3 / k 2 . Obviamente, sabemos que todas as funções em A C 0 podem ser eliminadas corrigindo todas as variáveis, exceto n 1 / d , para alguma constante d 2 . Mas, para obter um n 2 limite inferior seria suficiente para encontrar uma função explícita em A C 0 , que não pode ser morto, fixando todos, mas, digamos, n 1 / 2F(X)n3/k2AC0 n1/dd2n2AC0n1/2variáveis. Deve-se procurar essa função em profundidade maior que duas.

Na verdade, para a função como acima, pode-se obter limites inferiores sobre n 2 / log n através de um simples argumento ganancioso, sem Nechiporuk, sem Subbotovskaya e sem restrições aleatórias! Para isso, basta que a "função interna" g (Y) seja não trivial (depende de todas as suas variáveis n / b ). Além disso, o limite é válido para qualquer base de portas de ventilador constantes, não apenas para as fórmulas de De Morgan.F(X)n2/lognn/b

Prova: Dada uma fórmula para com s folhas, selecione em cada bloco X i uma variável que apareça o menor número de vezes que uma folha. Em seguida, defina todas as variáveis ​​restantes para as constantes correspondentes, de modo que cada g ( X i ) gire para uma variável ou sua negação. A fórmula obtida será então pelo menos n / b vezes menor que a fórmula original. Assim, s é pelo menos n / b = n / log nF(X)sXig(Xi)n/bsn/b=n/lognvezes o tamanho da fórmula de f , ou seja, s n 2 - o ( 1 ) . QED2b/logb=n/loglognfsn2o(1)

Para obter ou mais, é necessário incorporar o efeito de encolhimento de Subbotovskaya-Hastad sob restrições aleatórias. Um possível candidato poderia ser alguma versão da função de Sipser usada por Hastad para mostrar que os circuitos de profundidade ( d + 1 ) são mais poderosos do que os da profundidade d .n2(d+1)d

Stasys
fonte