Límites inferiores del tamaño de la fórmula para funciones AC0

Pregunta:

¿Cuál es el límite inferior de tamaño de fórmula más conocido para una función explícita en AC ⁰ ? ¿Existe una función explícita con un límite inferior ?$\Omega(n^2)$

Fondo:

Como la mayoría de los límites inferiores, los límites inferiores del tamaño de la fórmula son difíciles de encontrar. Estoy interesado en los límites inferiores del tamaño de la fórmula sobre el conjunto de compuerta universal estándar {AND, OR, NOT}.

El límite inferior del tamaño de fórmula más conocido para una función explícita sobre este conjunto de compuertas es para una función definida por Andreev. Este límite fue demostrado por Håstad, mejorando el límite inferior de Andreev de Ω ( n 2.5 - o ( 1 ) ) . Otro límite inferior explícito es el límite inferior de Khrapchenko Ω ( n 2 ) para la función de paridad.$\Omega(n^{3-o(1)})$$\Omega(n^{2.5-o(1)})$$\Omega(n^2)$

Sin embargo, estas dos funciones no están en AC ⁰ . Me pregunto si conocemos una función explícita en AC ⁰ con un límite inferior cuadrático (o mejor). El mejor límite que conozco es el límite inferior de para la función de distinción de elementos, como lo muestra Nechiporuk. Tenga en cuenta que la función de distinción de elementos está en AC ⁰ , por lo que estoy buscando un límite inferior para una función AC ⁰ explícita que sea mejor que Ω ( n 2 / log n ) , preferiblemente Ω ( n 2 ) .$\Omega(n^2/\log n)$$\Omega(n^2/\log n)$$\Omega(n^2)$

Otras lecturas:

Un recurso excelente sobre el tema es "Complejidad de la función booleana: avances y fronteras" de Stasys Jukna. Un borrador del libro está disponible de forma gratuita en su sitio web.

Una buena pregunta! Khrapchenko definitivamente no puede dar límites inferiores cuadráticos para las funciones . Su límite inferior es, de hecho, al menos un cuadrado de sensibilidad media. Y todas las funciones en A C 0 tienen una sensibilidad media polilogarítmica. Aparentemente, Subbotovskaya-Andreev tampoco puede dar esa función porque el argumento que utilizan (la restricción aleatoria da como resultado fórmulas mucho más pequeñas) es exactamente la razón que obliga a un gran tamaño de circuito A C 0 ; Lema cambiante de Hastad (no estoy muy seguro, solo una intuición). La única esperanza es Nechiporuk. Pero su argumento no puede dar más de n 2 / log $AC^0$$AC^0$$AC^0$$n^2/\log n$, por razones teóricas de información. Entonces, ¿puede ser que todo en tenga fórmulas de tamaño cuadrático (o incluso más pequeño)? No creo en ello, pero no pude encontrar rápidamente un contraejemplo. $AC^0$

En realidad, el fenómeno de Allender-Koucky surge también en otro contexto, en la complejidad de los gráficos. Digamos que un circuito de variables representa un gráfico bipartito n × n G en vértices V = { 1 , ... , 2 n } si para cada vector de entrada a con exactamente dos 1s es, digamos, las posiciones i y j ( i ≤ n , j > n ) el circuito acepta un iff vértices i y $2n$$n\times n$$G$$V=\{1,\ldots,2n\}$$a$$i$$j$$i\leq n$$j>n$$a$$i$$j$son adyacentes en . Problema: exhiba un gráfico explícito G que requiera que al menos n ϵ puertas estén representadas por un circuito monótono Σ 3 . Parece que una pregunta inocente (ya que la mayoría de los gráficos requieren alrededor de n 1 / 2 puertas. Pero cualquier gráfico nos daría una función booleana de 2 m = 2 log n variables de que requieren no monótono circuitos de registro a fondo de tamaño superlinear (por resultados de Valiant) Por lo tanto, incluso probar n ϵ límites inferiores para circuitos de profundidad 3 puede ser un desafío. $G$$G$$n^{\epsilon}$ $\Sigma_3$$n^{1/2}$$2m=2\log n$$n^{\epsilon}$

¡Gracias, Kaveh, por desear mirar los capítulos sobre la complejidad de la prueba!

Con respecto a la pregunta de Robin, primero esa nota contiene funciones que requieren fórmulas (e incluso circuitos) de tamaño n k para cualquier constante k . Esto se deduce, por ejemplo, de un simple hecho de que A C 0 contiene todos los DNF con monomios constantemente largos. Por lo tanto, A C 0 contiene al menos exp ( n k ) funciones distintas, para cualquier k . Por otro lado, tenemos como máximo funciones exp ( t log n ) computables por fórmulas de tamaño $AC^0$ $n^k$$k$$AC^0$$AC^0$$\exp(n^k)$$k$$\exp(t\log n)$$t$.

Discutí brevemente el tema de obtener límites inferiores explícitos de o mayores con Igor Sergeev (de la universidad de Moscú). Una posibilidad podría ser usar el método de Andreev, pero aplicado a otra función computable más fácil en lugar de Parity. Es decir, considerar una función de n variables de la forma F ( X ) = f ( g ( X 1 ) , ... , g ( X b ) ) , donde b = log n y g es una función en $n^2$$n$$F(X)=f(g(X_1),\ldots,g(X_b))$$b=\log n$$g$ de n / b variables; f es la función más compleja de lasvariables b (la mera existencia de f es suficiente). Solo necesitamos que la función g no se pueda "matar" en el siguiente sentido: si arreglamos todas lasvariablesexcepto k en X , entonces debe ser posible arreglar todas menos una de las variables restantes de g para que la subfunción obtenida de g Es una sola variable. Entonces aplicar el argumento de Andreev y usando el resultado de Hastad que la constante de contracción es de al menos 2 (no sólo 3 /$AC^0$$n/b$$f$$b$$f$$g$$k$$X$$g$$g$$2$$3/2$como se mostró anteriormente por Sybbotovskaya), el límite inferior resultante para será aproximadamente n 3 / k 2 . Por supuesto, sabemos que todas las funciones en A C 0 pueden eliminarse arreglando todas las variables excepto n 1 / d , para algunas constantes d ≥ 2 . Pero para conseguir un n 2 límite inferior sería suficiente para encontrar una función explícita en A C 0 que no puede ser matado por la fijación de todos, pero, por ejemplo, n 1 /$F(X)$$n^3/k^2$$AC^0$ $n^{1/d}$$d\geq 2$$n^2$$AC^0$$n^{1/2}$variables Uno debería buscar dicha función en profundidad más grande que dos.

$F(X)$$n^2/\log n$$n/b$

$F(X)$$s$$X_i$$g(X_i)$$n/b$$s$$n/b=n/\log n$$2^b/\log b=n/\log\log n$$f$$s\geq n^{2-o(1)}$

$n^2$$(d+1)$$d$