Limites inférieures de la taille de la formule pour les fonctions AC0

Question:

Quelle est la limite inférieure de taille de formule la plus connue pour une fonction explicite dans AC ⁰ ? Existe-t-il une fonction explicite avec une borne inférieure $\Omega(n^2)$ ?

Contexte:

Comme la plupart des limites inférieures, les limites inférieures de la taille de la formule sont difficiles à trouver. Je m'intéresse aux limites inférieures de la taille de la formule par rapport à l'ensemble de portes universel standard {AND, OR, NOT}.

La borne inférieure de la taille de formule la plus connue pour une fonction explicite sur cet ensemble de portes est $\Omega(n^{3-o(1)})$ pour une fonction définie par Andreev. Cette borne a été montrée par Håstad, améliorant la borne inférieure d'Andreev de $\Omega(n^{2.5-o(1)})$ . Une autre borne inférieure explicite est la borne inférieure Khrapchenko $\Omega(n^2)$pour la fonction de parité.

Cependant, ces deux fonctions ne sont pas en AC ⁰ . Je me demande si nous connaissons une fonction explicite dans AC ⁰ avec une borne inférieure quadratique (ou mieux). La meilleure limite que je connaisse est la borne inférieure $\Omega(n^2/\log n)$ pour la fonction de distinction d'élément, comme le montre Nechiporuk. Notez que la fonction de distinction d'élément est dans AC ⁰ , donc je cherche une borne inférieure pour une fonction AC ⁰ explicite meilleure que $\Omega(n^2/\log n)$ , de préférence $\Omega(n^2)$ .

Lectures complémentaires:

Une excellente ressource sur le sujet est "Complexité de la fonction booléenne: avancées et frontières" par Stasys Jukna. Un brouillon du livre est disponible gratuitement sur son site Internet.

Une belle question! Khrapchenko ne peut certainement pas donner de bornes inférieures quadratiques pour les fonctions . Sa borne inférieure est en fait au moins carrée de sensibilité moyenne. Et toutes les fonctions dans A C 0 ont une sensibilité moyenne poly-logarithmique. Subbotovskaya-Andreev ne peut apparemment pas non plus donner une telle fonction parce que l'argument qu'ils utilisent (résultats de restriction aléatoires dans des formules beaucoup plus petites) est exactement la raison pour laquelle une grande taille de circuit A C 0 est forcée; Switching Lemma de Hastad (je ne suis pas sûr, juste une intuition). Le seul espoir est Nechiporuk. Mais son argument ne peut pas donner plus de n 2 / log $AC^0$$AC^0$$AC^0$$n^2/\log n$, pour des raisons théoriques de l'information. Alors, est-ce que tout dans a des formules de taille quadratique (ou même plus petite)? Je n'y crois pas, mais je n'ai pas pu trouver rapidement un contre-exemple. $AC^0$

En fait, le phénomène Allender-Koucky se pose également dans un autre contexte - dans la complexité des graphes. Dire qu'un circuit de des variables représente un bipartite n × n graphe G de sommets V = { 1 , ... , 2 n } si pour chaque vecteur d' entrée un avec exactement deux 1 est, par exemple, les positions i et j ( i ≤ n , j > n ) le circuit accepte a si les sommets i et $2n$$n\times n$$G$$V=\{1,\ldots,2n\}$$a$$i$$j$$i\leq n$$j>n$$a$$i$$j$sont adjacents dans . Problème: présenter un graphe explicite G nécessitant au moins n ϵ portes d'être représenté par un circuit monotone Σ 3 . On dirait une question innocente (puisque la plupart des graphiques nécessitent environ n 1 / 2 portes. Mais un tel graphe nous donnerait une fonction booléenne de 2 m = 2 log n variables placées non-monotones circuits log-profondeur de taille surlinéaire (par les résultats de Ainsi, même prouver n ϵ bornes inférieures pour les circuits de profondeur 3 peut être un défi. $G$$G$$n^{\epsilon}$ $\Sigma_3$$n^{1/2}$$2m=2\log n$$n^{\epsilon}$

Merci, Kaveh, d'avoir souhaité consulter les chapitres sur la complexité des preuves!

Concernant la question de Robin, d'abord que la note contient des fonctions nécessitant des formules (et même des circuits) de taille n k pour toute constante k . Cela découle, par exemple, d'un simple fait que A C 0 contient tous les DNF avec des monômes constamment longs. Ainsi, A C 0 contient au moins exp ( n k ) fonctions distinctes, pour tout k . D'un autre côté, nous avons tout au plus des fonctions exp ( t log n ) calculables par des formules de taille $AC^0$ $n^k$$k$$AC^0$$AC^0$$\exp(n^k)$$k$$\exp(t\log n)$$t$.

J'ai brièvement discuté de la question de l'obtention de limites inférieures explicites de ou plus avec Igor Sergeev (de l'université de Moscou). Une possibilité pourrait être d'utiliser la méthode d'Andreev, mais appliquée à une autre fonction calculable plus facile au lieu de Parité. Autrement dit, considérons une fonction de n variables de la forme F ( X ) = f ( g ( X 1 ) , … , g ( X b ) ) où b = log n et g est une fonction dans $n^2$$n$$F(X)=f(g(X_1),\ldots,g(X_b))$$b=\log n$$g$ de n / b variables; f est la fonction la plus complexe desvariables b (la simple existence de f suffit). Nous avons seulement besoin que la fonction g ne puisse pas être "tuée" dans le sens suivant: si nous fixons toutes lesvariablessauf k dans X , alors il doit être possible de fixer toutes les variables de g sauf une, desorte que la sous-fonction obtenue de g est une variable unique. Ensuiteapplicationl'argument de Andreev etutilisant le résultat de Hastad que la constante diminution estau moins 2 (pas seulement 3 /$AC^0$$n/b$$f$$b$$f$$g$$k$$X$$g$$g$$2$$3/2$comme indiqué précédemment par Sybbotovskaya), la limite inférieure résultante pour sera d'environ n 3 / k 2 . Bien sûr, nous savons que chaque fonction dans A C 0 peut être supprimée en fixant toutes les variables sauf n 1 / d , pour une constante d ≥ 2 . Mais pour obtenir un n 2 minorant il suffirait de trouver une fonction explicite dans un C 0 qui ne peut être tué en fixant tous , mais, disons, n 1 /$F(X)$$n^3/k^2$$AC^0$ $n^{1/d}$$d\geq 2$$n^2$$AC^0$$n^{1/2}$variables. Il faut rechercher une telle fonction en profondeur supérieure à deux.

En fait, pour la fonction comme ci-dessus, on peut obtenir des bornes inférieures sur n 2 / log n via un simple argument gourmand, pas de Nechiporuk, pas de Subbotovskaya et pas de restrictions aléatoires! Pour cela, il suffit simplement que la "fonction interne" g (Y) soit non triviale (dépend de toutes ses variables n / b ). De plus, la limite est valable pour toute base de ventilations constantes, pas seulement pour les formules De Morgan.$F(X)$$n^2/\log n$$n/b$

Preuve: Étant donné une formule pour avec s feuilles, sélectionnez dans chaque bloc X i une variable qui apparaît le moins de fois sous forme de feuille. Réglez ensuite toutes les variables restantes sur les constantes correspondantes de sorte que chaque g ( X i ) se transforme en variable ou sa négation. La formule obtenue sera alors au moins n / b fois plus petite que la formule d'origine. Ainsi, s est au moins n / b = n / log $F(X)$$s$$X_i$$g(X_i)$$n/b$$s$$n/b=n/\log n$fois la taille de la formule de f , c'est-à-dire s ≥ n 2 - o ( 1 ) . QED$2^b/\log b=n/\log\log n$$f$$s\geq n^{2-o(1)}$

Pour obtenir ou plus, il faut incorporer l'effet de rétrécissement de Subbotovskaya-Hastad sous des restrictions aléatoires. Un candidat possible pourrait être une version de la fonction de Sipser utilisée par Hastad pour montrer que les circuits de profondeur ( d + 1 ) sont plus puissants que ceux de profondeur d .$n^2$$(d+1)$$d$