État sur les limites inférieures du circuit pour les circuits de profondeur bornés par polylog

La complexité des circuits en profondeur bornée est l'un des principaux domaines de recherche de la théorie de la complexité des circuits. Cette rubrique a des origines dans des résultats comme "la fonction de parité n'est pas dans " et "la fonction mod n'est pas calculée par ", où est la classe des langages décidables par une profondeur non uniforme, constante, une taille polynomiale, un fan-in illimité ET, OU, NON et des portes modulo , où . Cependant, obtenir des résultats concrets aux bornes inférieures sur des circuits de profondeur polylogarithmiques semble être hors de portée en utilisant des méthodes classiques comme la restriction des entrées et l'approximation des polynômes sur les champs finis.$AC^{0}$$p$$AC^{0}[q]$$AC^0[q]$$q$$\gcd(p,q)=1$

Je connais un article STOC'96 qui mène à la théorie de la complexité géométrique et qui montre qu'un calcul parallèle efficace utilisant des opérations sans bit par bit ne peut pas calculer le problème de flux de coût min.

Cela signifie que dans certains paramètres limités, nous pouvons prouver les limites inférieures $NC$ pour certains problèmes $P$ complets.

Premièrement, existe-t-il d'autres méthodes ou techniques qui peuvent être des approches plausibles pour prouver les limites inférieures du circuit de profondeur polylogarithmique?

Deuxièmement, quelle est l'utilité de l'énoncé suivant pour la communauté des théoriciens?

La taille d'un circuit $NC$ calculant une fonction booléenne $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ est au moins $l$ , où $l$ est une quantité mathématique en fonction de la dureté du fonction cible $f$ . La valeur de $l$ peut être, par exemple, une quantité combinatoire comme un écart, une quantité algébrique linéaire comme le rang d'un certain type de matrice sur un champ, ou une quantité entièrement nouvelle qui n'a pas été utilisée auparavant dans la théorie de la complexité.

Concernant les techniques permettant de prouver les limites inférieures de la profondeur du circuit poly-log, toutes les approches actuelles fonctionnent dans des paramètres restreints . Comme dans le travail menant à GCT que vous mentionnez, la limite inférieure s'applique à un modèle PRAM restreint sans opérations sur les bits.

Sous une autre restriction, qui est la restriction monotone pour les fonctions booléennes monotones, il existe une approche analytique de Fourier (ou combinatoire énumérative) pour prouver les limites inférieures de la profondeur du circuit monotone, dans mon travail conjoint avec Aaron Potechin ( ECCC et STOC ). Cela améliore un résultat antérieur de Ran Raz et Pierre McKenzie, qui étend le cadre du jeu de communication de Mauricio Karchmer et Avi Wigderson concernant la profondeur du circuit.

Une autre ligne de recherche pour étendre le jeu Karchmer – Wigderson a été proposée comme jeu de communication référencé par Scott Aaronson et Avi Wigderson, dont l'extension à un protocole de prouveur concurrent est suggérée comme une approche pour séparer NC de P par Gillat Kol et Ran Raz ( ECCC et ITCS ).

Outre l'étude de la restriction syntaxique de la monotonie, il existe une approche pour étudier une restriction sémantique liée aux jeux de galets (appelés programmes de ramification économe) par Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman et Rahul Santhanam. Il y a une forte limite inférieure sous la restriction économe de Dustin Wehr, correspondant à la limite supérieure la plus connue pour les problèmes de P-complet. Ces résultats concernent la complexité de l'espace déterministe, qui abaisse le temps parallèle aux limites ou la profondeur du circuit par des résultats de simulation connus (par exemple depuis ).$\text{AlternatingTime}[t] \subseteq \text{DeterministicSpace}[t]$

Concernant la question relative à la taille et à la profondeur des circuits, l'approche suivante peut être liée. Richard Lipton et Ryan Williams montrent que, étant donné une limite inférieure suffisamment forte sur la profondeur (ie ), une borne inférieure de faible taille (ie n 1 + Ω ( 1 ) ) peut séparer NC de P. Ce résultat découle d'un argument de compromis taille-profondeur basé sur des simulations respectant les blocs. Un résultat antérieur sur la profondeur de négociation pour la taille est dû à Allender et Koucký basé sur l'idée d'auto-réductibilité, mais il a étudié des classes de complexité plus petites comme NC 1 et NL.$n^{1-O(1)}$$n^{1+\Omega(1)}$$^1$

Notez que parmi les approches mentionnées ci-dessus, certaines d'entre elles prennent en compte à la fois la taille et la profondeur des circuits, tandis que d'autres approches ne considèrent que la profondeur du circuit. En particulier, l’approche semi-algébro-géométrique de Mulmuley , l’approche par protocole de preuve concurrente étudiée par Kol – Raz et l’ approche par compromis taille-profondeur d’ Allender – Koucký et Lipton – Williams concernent toutes à la fois la taille et la profondeur des circuits. Les résultats de Chan – Potechin , Raz – McKenzie , Cook – McKenzie – Wehr – Braverman – Santhanam et Wehr donnent des limites inférieures de profondeur de circuit dans des paramètres restreints, quelle que soit la taille. Aussi, le jeu de communication référencé deAaronson – Wigderson ne concerne que la profondeur du circuit.

Il est toujours cohérent avec nos connaissances qu'un certain problème P-complet ne peut pas être calculé par des circuits de faible profondeur (ie ), quelle que soit leur taille. Si la taille n'a pas d'importance pour les circuits de faible profondeur (de fan-in borné), alors il est peut-être logique de se concentrer davantage sur la profondeur du circuit que de se concentrer sur la taille des circuits de faible profondeur.$\log^{O(1)}n$

Suite à la suggestion de Kaveh, je mets mon commentaire en tant que réponse (élargie).

Concernant $Q1$ , une mise en garde s'impose: même profondeur logarithmique si loin d'être comprise, sans parler de poly-logarithmique. Donc, dans le monde non monotone, le vrai problème est beaucoup moins ambitieux:

Battre la profondeur de log Problème: Démontrer une borne inférieure super-linéaire (!) Pour les circuits . $NC^1$

Le problème reste ouvert (depuis maintenant plus de 30 ans) même pour les circuits linéaires . Ce sont des circuits de fanin- 2 sur la base { ⊕ , 1 } , et ils calculent des transformations linéaires f ( x ) = A x sur G F ( 2 ) . Un comptage facile montre que presque toutes les matrices A nécessitent des portes Ω ( n 2 / log n ) , à n'importe quelle profondeur. $NC^1$$2$$\{\oplus,1\}$$f(x)=Ax$$GF(2)$$A$$\Omega(n^2/\log n)$

Concernant $Q2$ : Oui, nous avons quelques mesures algébriques / combinatoires, des bornes inférieures sur lesquelles battraient les circuits de profondeur de log. Malheureusement, jusqu'à présent, nous ne pouvons pas prouver des limites suffisamment grandes pour ces mesures. Par exemple, pour linéaire -circuits, une telle mesure est la rigidité R A ( r ) de la matrice A . Il s'agit du plus petit nombre d'entrées de A qu'il faut modifier pour réduire le rang à r . Il est facile de montrer que R A ( r ) ≤ ( n $NC^1$ $R_A(r)$$A$$A$$r$ est valable pour chaquematricebooléenne n × n A , et Valiant (1977) a montré que cette limite est serrée pour presque toutes les matrices. Pour battrecircuits log-profondeur, il suffit de présenter une séquence de boolean n × n matrices A de telle sorte que$R_A(r)\leq (n-r)^2$$n\times n$$A$$n\times n$$A$

pour les constantes ϵ , δ > 0 . $R_A(\epsilon n)\geq n^{1+\delta}$$\epsilon,\delta>0$

Les meilleures que nous connaissions jusqu'à présent sont les matrices avec R A ( r ) ≥ ( n 2 / r ) log ( n / r ) . Pour les matrices Sylvester (c'est-à-dire les matrices de produits internes), la borne inférieure de Ω ( n 2 / r ) est facile à montrer . $A$$R_A(r)\geq (n^2/r)\log(n/r)$$\Omega(n^2/r)$

Nous avons des mesures combinatoires pour général (non linéaire) -circuits, aussi bien pour un biparti n × n graphe G , nous allons t ( G ) soit le plus petit nombre t tel que G peut être écrit comme une intersection de t biparti graphiques, chacun étant une union d'au plus t graphes bipartites complets. Pour battre les circuits généraux de profondeur de log, il suffirait de trouver une séquence de graphiques avec$NC^1$$n\times n$$G$$t(G)$$t$$G$$t$$t$

pour une constante ϵ > $t(G_n)\geq n^{\epsilon}$$\epsilon >0$

(voir par exemple ici comment cela se produit). Encore une fois, presque tous les graphiques ont . Cependant, le meilleur reste une limite inférieure t ( G ) ≥ log 3 n pour les matrices Sylvester, en raison de Lokam . $t(G)\geq n^{1/2}$$t(G)\geq \log^3 n$

Enfin, permettez-moi de mentionner que nous avons même une mesure combinatoire "simple" (quantité) une borne inférieure faible (linéaire) sur laquelle donnerait des bornes inférieures même exponentielles (!) Pour les circuits non monotones. Pour un biparti graphe G , que c ( G ) soit le plus petit nombre de fanin- 2 union ( ∪ ) et l' intersection ( ∩ opérations) nécessaires pour produire G lors du démarrage des étoiles; une étoile est un ensemble d'arêtes reliant un sommet à tous les sommets de l'autre côté. Presque tous les graphiques ont c ( G ) = Ω ( n $n\times n$$G$$c(G)$$2$$\cup$$\cap$$G$ . En revanche, une borne inférieure de$c(G)=\Omega(n^2/\log n)$

pour une constante ϵ > $c(G_n)\geq (4+\epsilon)n$$\epsilon>0$

impliquerait une borne inférieure sur la complexité du circuit non monotone d'une fonction booléenne explicite f G de N variables. Si G est un graphique n × m avec m = o ( n ) , alors même une borne inférieure c ( G n ) ≥ ( 2 + ϵ ) n suffit (encore une fois, voir par exemple ici comment cela se produit). Limites inférieures c ( $\Omega(2^{N/2})$$f_G$$N$$G$$n\times m$$m=o(n)$$c(G_n)\geq (2+\epsilon)n$ peut être affiché pour des graphiques relativement simples. Le problème, cependant, est de le faire avec " - ϵ " remplacé par " + ϵ ". Des mesures plus combinatoires de la complexité des circuits à limite inférieure (y compris les circuits A C C ) peuvent être trouvées dans le livre. $c(G)\geq (2-\epsilon)n$$-\epsilon$$+\epsilon$$ACC$

PS Alors, sommes-nous par un facteur constant de de montrer P ≠ N P ? Bien sûr que non. J'ai mentionné cette dernière mesure c ( G ) uniquement pour montrer qu'il faut traiter "l'amplification" (ou "grossissement") des limites inférieures avec une bonne part de scepticisme: même si les limites dont nous avons besoin semblent "innocentes", elles sont beaucoup plus petites ( linéaire) que presque tous les graphiques nécessitent (quadratique), la difficulté inhérente de prouver une borne inférieure (faible) peut être encore plus grande. Bien sûr, après avoir trouvé une mesure combinatoire, nous pouvons dire quelque chose sur les propriétés des fonctions qui les rendent difficiles à calculer. Cela peut être utile pour prouver une indirecte$2+\epsilon$$P\neq NP$$c(G)$borne inférieure: une classe de complexité contient une fonction nécessitant de grands circuits ou formules. Mais le but ultime est de trouver une fonction dure explicite , dont la définition n'a pas une "odeur algorithmique", n'a pas d'aspects de complexité cachés.