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 ?
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 )
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 .Ω ( n 2 )
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.
fonte
Respostas:
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 nAC0 AC0 AC0 n2/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 j2n n×n G V={1,…,2n} a i j i≤n j>n a i j sã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. G G nϵ Σ3 n1/2 2m=2logn nϵ
fonte
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 nk k AC0 AC0 exp(nk) k exp(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 An2 n F(X)=f(g(X1),…,g(Xb)) b=logn g 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 / 2AC0 n/b f b f g k X g g 2 3/2 como 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/k2 AC0 n1/d d≥2 n2 AC0 n1/2 variá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/logn n/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) s Xi g(Xi) n/b s n/b=n/logn vezes o tamanho da fórmula de f , ou seja, s ≥ n 2 - o ( 1 ) . QED2b/logb=n/loglogn f s≥n2−o(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
fonte