Explication de la théorie de la complexité géométrique dans le style de Wikipedia

Quelqu'un peut-il fournir une explication concise de l'approche GCT de Mulmuley compréhensible par les non-experts? Une explication qui conviendrait pour une page Wikipedia sur le sujet (qui est stub pour le moment).

Motivation: Je suis en train de "co-lire" l'ouvrage de Scott Aaronson sur l'informatique quantique depuis Democritus avec un ami à moi qui est chercheur en théorie des cordes. Dans la préface du livre, Aaronson appelle GCT "la théorie des cordes de l'informatique". En tant que théoricien des cordes, mon ami s'est enthousiasmé pour cette affirmation et m'a demandé ce qu'est GCT. À ce stade, j'ai honteusement réalisé que je n'avais pas de réponse prête pour Wikipedia pour sa question.

Je ne sais pas exactement quel niveau convient à un article de Wikipedia (différents articles semblent viser différents niveaux d'expertise) ni à ce que vous recherchez. Alors voici un essai, mais je suis ouvert aux commentaires.

La théorie de la complexité géométrique propose d'étudier la complexité de calcul des fonctions de calcul (par exemple des polynômes) en exploitant les symétries inhérentes à la complexité et toute symétrie supplémentaire des fonctions à l'étude.

Comme beaucoup d’approches précédentes, l’objectif ultime est de séparer deux classes de complexité en montrant qu’il existe un polynôme qui prend les fonctions en entrée (par exemple , par leurs vecteurs de coefficients) tels que disparaisse sur chaque fonction mais ne disparaisse pas sur une fonction . pfpf∈ C e a s y g h a r d ∈ C h a r $\mathcal{C}_{easy}, \mathcal{C}_{hard}$$p$$f$$p$$f \in \mathcal{C}_{easy}$$g_{hard} \in \mathcal{C}_{hard}$

La première idée clé (cf. [GCT1, GCT2]) est d'utiliser des symétries pour organiser non les fonctions elles-mêmes, mais pour organiser les propriétés ( algébro-géométriques ) de ces fonctions, telles que capturées par des polynômes tels que ci-dessus. Cela permet d'utiliser la théorie de la représentation pour tenter de trouver un tel . Des idées similaires concernant la théorie de la représentation et la géométrie algébrique avaient déjà été utilisées en géométrie algébrique auparavant, mais à ma connaissance, jamais de cette façon.$p$$p$

La deuxième idée clé (cf. [GCT6]) est de trouver des algorithmes combinatoires (et polynomiaux) pour les problèmes résultants de la théorie de la représentation, puis de procéder au reverse engineering de ces algorithmes pour montrer qu'un tel existe. Cela peut être pris dans l’esprit d’utiliser la programmation linéaire (un algorithme) pour prouver certaines déclarations purement combinatoires.$p$

En effet, [GCT6] suggère de réduire les problèmes de représentation ci-dessus à des problèmes de programmation entiers , puis de montrer que les adresses IP résultantes sont résolues par leurs relaxations de LP, et de donner des algorithmes combinatoires pour les LP résultants. Les conjectures de [GCT6] sont elles-mêmes motivées par une ingénierie inverse des résultats connus des coefficients de Littlewood-Richardson, un problème analogue mais plus facile en théorie de la représentation. Dans le cas des coefficients LR, la règle combinatoire de Littlewood-Richardson est apparue en premier. Plus tard, Berenstein et Zelevinsky [BZ] ainsi que Knutson et Tao [KT] (voir [KT2] pour un aperçu convivial) donnèrent un IP pour les coefficients LR. Knutson et Tao ont également prouvé la conjecture de saturation, ce qui implique que l'IP est résolu par sa relaxation LP (cf. [GCT3, BI]).

Les résultats de [GCT5] montrent que le lemme de normalisation de Noether, qui est explicitement dénormalisé , est essentiellement équivalent au problème ouvert notoire de la théorie de la complexité de la dérandomisation en boîte noire du test d'identité polynomiale . En gros, cela correspond au programme plus large si trouver une base explicite pour les fonctions qui disparaissent (ne disparaissent pas) sur (dans ce cas, la classe pour laquelle le déterminant est complet) pourrait être: utilisé pour dériver une règle combinatoire pour le problème souhaité en théorie de la représentation, comme cela s’est passé dans d’autres contextes en géométrie algébrique. Une étape intermédiaire ici serait de trouver une base pour ceux qui (ne pas) disparaître sur la normalisation desC e a s y p C e a s $p$$\mathcal{C}_{easy}$$p$$\mathcal{C}_{easy}$ , qui est par construction une variété algébrique plus agréable - en d’autres termes, pour dérandonner le lemme de normalisation de Noether pour le DET.

Exemples de symétries de complexité et de fonctions

Par exemple, la complexité d'une fonction - pour les notions de complexité les plus naturelles - reste inchangée si nous permutons les variables par une certaine permutation . Ainsi, les permutations sont des symétries de la complexité elle-même. Pour certaines notions de complexité (comme dans la complexité de circuits algébriques), tous les changements linéaires inversibles des variables sont des symétries.f ( x π ( 1 ) , … , x π ( n ) ) $f(x_1, \dotsc, x_n)$$f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$$\pi$

Les fonctions individuelles peuvent avoir des symétries supplémentaires. Par exemple, le déterminant a les symétries pour toutes les matrices telles que . (D'après ce que j'ai peu appris à ce sujet, je suppose que cela est analogue au phénomène de rupture de symétrie spontanée en physique.)$\det(X)$$\det(AXB) = \det(X^{T}) = \det(X)$$A,B$$\det(AB) = 1$

Quelques progrès récents [cette section est certes incomplète et technique, mais un compte rendu complet prendrait des dizaines de pages ... Je voulais simplement souligner quelques progrès récents]

Burgisser et Ikenmeyer [BI2] ont montré une borne inférieure sur la multiplication matricielle à la suite du programme GCT jusqu'à utiliser des représentations avec des multiplicités nulles et non nulles. Landsberg et Ottaviani [LO] ont donné la limite inférieure la plus connue, essentiellement , au rang de frontière de la multiplication matricielle en utilisant la théorie de la représentation pour organiser les propriétés algébriques, mais sans utiliser de multiplicités de représentation ni de règles combinatoires.$\frac{3}{2}n^2$$2n^2$

Le problème suivant après les coefficients de Littlewood-Richardson est celui de Kronecker . Celles-ci se retrouvent à la fois dans une série de problèmes dont on pense qu’ils vont éventuellement atteindre les problèmes de la théorie de la représentation apparaissant dans le GCT, et plus directement en tant que limites des multiplicités dans l’approche du GCT pour la multiplication matricielle et le déterminant permanent. Trouver une règle combinatoire pour les coefficients de Kronecker est un problème ouvert de longue date en théorie de la représentation; Blasiak [B] a récemment donné une telle règle combinatoire pour les coefficients de Kronecker avec une forme de crochet.

Kumar [K] a montré que certaines représentations apparaissent dans l'anneau de coordonnées du déterminant avec une multiplicité non nulle, en supposant la conjecture carrée de la colonne latine (cf. Huang-Rota et Alon-Tarsi; cette conjecture n'apparaît peut-être pas aussi par coïncidence, dans [BI2 ]). Par conséquent, ces représentations ne peuvent pas être utilisées pour séparer permanent de déterminant sur la base de multiplicités zéro vs non nul, bien qu'il soit encore possible de les utiliser pour séparer permanent de déterminant par une inégalité plus générale entre les multiplicités.

Références [B] J. Blasiak. Coefficients de Kronecker pour une forme de crochet. arXiv: 1209.2018, 2012.

[BI] P. Burgisser et C. Ikenmeyer. Un algorithme max-flow pour la positivité des coefficients de Littlewood-Richardson. FPSAC 2009.

[BI2] P. Burgisser et C. Ikenmeyer. Limites inférieures explicites via la théorie de la complexité géométrique. arXiv: 1210.8368, 2012.

[BZ] AD Berenstein et AV Zelevinsky. Triple multiplicités pour et le spectre de l'algèbre extérieure de la représentation adjointe. $\mathfrak{sl}(r+1)$J. Combiné algébrique. 1 (1992), no. 1, 7-22.

[GCT1] KD Mulmuley et M. Sohoni. Théorie de la complexité géométrique I: une approche du problème P vs NP et des problèmes connexes. SIAM J. Comput. 31 (2), 496-526, 2001.

[GCT2] KD Mulmuley et M. Sohoni. Théorie de la complexité géométrique II: vers des obstacles explicites aux plongées parmi les variétés de classe. SIAM J. Comput., 38 (3), 1175-1206, 2008.

[GCT3] KD Mulmuley, H. Narayanan et M. Sohoni. Théorie de la complexité géométrique III: sur la décision de ne pas éliminer un coefficient de Littlewood-Richardson. J. Combiné algébrique. 36 (2012), no. 1, 103-110.

[GCT5] KD Mulmuley. Théorie de la complexité géométrique V: équivalence entre la dépromination de la boîte noire du test d'identité polynomial et la dépromérisation du lemme de normalisation de Noether. FOCS 2012, également arXiv: 1209.5993.

[GCT6] KD Mulmuley. Théorie de la complexité géométrique VI: le retournement via la positivité. , Technical Report, département Computer Science, Université de Chicago, janvier 2011.

[K] S. Kumar. Etude des représentations supportées par la fermeture en orbite du déterminant. arXiv: 1109.5996, 2011.

[LO] JM Landsberg et G. Ottaviani. Nouvelles limites inférieures pour le rang de frontière de la multiplication matricielle. arXiv: 1112.6007, 2011.

[KT] A. Knutson et T. Tao. Le modèle en nid d'abeille de produits tenseur . I. Preuve de la conjecture de saturation. $\text{GL}_n(\mathbb{C})$J. Amer. Math. Soc. 12 (1999), no. 4, 1055-1090.

[KT2] A. Knutson et T. Tao. Nid d'abeilles et sommes de matrices hermitiennes. Avis Amer. Math. Soc. 48 (2001), no. 2, 175–186.

J'ai récemment répondu à une question connexe sur Mathoverflow: https://mathoverflow.net/questions/277408/

Puisque ce site est peut-être un meilleur endroit, permettez-moi de répéter cette réponse ci-dessous. Les références à Joseph ou à Timothée concernent les autres messages relatifs à cette question de MO.

---

Soit une matrice générique et le polynôme homogène de degré donné par le déterminant. Soit qui prend la permanent d'une sous-matrice et multiplie par sa forme linéaire préférée afin de créer un autre polynôme homogène de degré (on pourrait également utiliser l'entrée au lieu de ). Cette modification s'appelle padding . Puis définir le nombre $X=(X_{ij})_{1\le i,j\le n}$$n\times n$$F_1(X)={\rm det}(X)$$n$

$$F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right]$$ $m\times m$$n$$X_{11}$$X_{nn}$ $$c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \}$$ où est agit sur l'espace affine de dimension où vies et sont des fermetures Zariski d'orbites. La grande conjecture de la région ou l'hypothèse de Valiant (une version complexe de ) est que croît plus vite que tout polynôme de .$G$$GL(n^2)$$n^2$$X$$\overline{G\cdot F_i}$${\rm P}\neq{\rm NP}$$c(m)$$m$

Maintenant, si , alors on a un surjectif - une carte equivariante entre les parties en degrés des anneaux de coordonnées de ces fermetures d’orbite. Le jeu consiste donc à essayer de montrer que cela ne se produit pas, car insuffisamment grand par rapport à en prouvant l’existence d’une obstruction de multiplicité , c’est-à-dire d’une représentation irréductible pour laquelle les multiplicités satisfont $\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$$G$

$$\mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d$$ $d$$n$$m$$\lambda$ $${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)$$ ou au niveau des idéaux $${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ .$$

Une approche optimiste consiste à montrer qu’il existe des obstructions d’occurrence , c’est-à-dire des telles que et . Cet espoir a été réduit à néant dans les travaux de Bürgisser, Ikenmeyer et Panova mentionnés par Timothy. Cependant, la possibilité d’obstructions multiples reste ouverte.$\lambda$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$

Je pense que l'approche de Mulmuley est d'essayer de prouver l'existence de telles obstructions de multiplicité en exploitant tous les outils disponibles de la théorie de la représentation pour le calcul de ces multiplicités. Personnellement, je n'ai jamais été fan de cette approche. Ayant étudié en profondeur la théorie invariante du XIXe siècle, il me semble plus naturel d’aborder le problème de la séparation orbite à l’aide des outils explicites de cette époque. Cet article de Gorchow semble également aller dans le même sens (je soupçonne que le troisième article mentionné par Joseph est dans la même veine). En langage classique (voir Turnbull ou Littlewood ), il faut explicitement construire un concomitant mixte qui disparaît sur$F_1$mais pas sur . Il faut aussi le faire infiniment souvent (en ) pour établir la propriété de croissance superpolynomiale. Un tel concomitant est identique à une carte -équivariante spécifique de votre modèle préféré pour la représentation irréductible à l'algèbre polynomiale dans les variables (Grochow appelle ce module séparateur ). Les théoriciens invariants du XIXe siècle avaient deux méthodes pour générer de tels objets: la théorie de l'élimination et l' algèbre schématique .$F_2$$m$$G$$\lambda$$n^2$$X$

Un très petit exemple où et sont des formes quartiques binaires sous l'action de (voir cette question MO ) est et Un concomitant séparant (ici, en fait, une covariante) est le hessien d’un octique binaire générique Il disparaît (à l'identique dans ) pour mais pas pour$F_1$$F_2$$G=SL(2)$

$$F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4$$ $$F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ .$$ $F$ $$H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ .$$ $x,y$$F=F_1$$F=F_2$. Dans ce cas, le hessien peut être vu comme une carte équivariante sous forme irréductible donnée par le second pouvoir symétrique (de la représentation bidimensionnelle fondamentale) dans l'anneau de coordonnées de l'espace affine des quartiques binaires.

Donc, un "plan" superoptimiste possible pour GCT implique la séquence suivante d'étapes.

1) Trouver un moyen de générer des tonnes de concomitants.

2) Identifier des candidats explicites pour la disparition sur et prouver cette propriété.$F_1$

3) Montrez qu'ils ne disparaissent pas sur .$F_2$

L'étape 1) est en principe résolue par le premier théorème fondamental pour mais il existe un décalage: le déterminant est un objet naturel dans la théorie des invariants pour (agissant sur les lignes et colonnes) plutôt que . On pourrait essayer de réparer le déséquilibre en exprimant le bloc de construction de base de la théorie invariante de en termes de celui de (voir cette question de MO pour un problème de réduction similaire. de à ).$GL(n^2)$$GL(n)\times GL(n)$$GL(n^2)$$GL(n^2)$$GL(n)\times GL(n)$$SL(n(n+1)/2)$$SL(n)$

Deviner les bons candidats pour l'étape 2) me semble difficile. Savoir au préalable que certaines multiplicités sont non nulles serait certainement utile. Bien que l'on puisse remettre à plus tard et reporter la preuve de la disparition non identique du concomitant à l'étape 3), ce qui devrait montrer plus que cela de toute façon. Si l'on a de tels candidats, il peut être facile de montrer qu'il disparaît sur par des arguments que l'on pourrait appeler le principe d'exclusion de Pauli (symétrisations de contrat avec antisymétrisation), propriété de grand nombre chromatique ou simplement «manque d'espace».${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$$F_1$

Cependant, je pense que la partie la plus difficile est l’étape 3). Par exemple, dans mon article intitulé "16 051 formules pour l'invariant des triples cubes par Ottaviani" avec Ikenmeyer et Royle, la conjecture a été effectuée par recherche informatisée, mais avec le bon candidat en main, l'explication sur était relativement facile à expliquer (c'est plutôt bel exemple de nombre chromatique dû aux propriétés globales du graphe plutôt qu’à une grosse clique). L'analogue de l'étape 3) dans notre article a été réalisé par calcul informatique à force brute et nous ne savons toujours pas pourquoi c'est vrai. Le problème paradigmatique lié à l’étape 3) est la conjecture Alon-Tarsi (voir cette question de MO et celle-ci).$F_1$aussi). À mon avis, il faut progresser sur ce type de question (le théorème des quatre couleurs l' est aussi, via une réduction due à Kauffman et Bar-Natan) avant la conjecture de Valiant.

Depuis la question est sur les percées dans GCT. Je pense que cet article de Landsberg et Ressayre mérite également une certaine attention puisqu'il suggère qu'une estimation raisonnable de la valeur exacte de est Notez que Bürgisser et Ikenmeyer ont donné dans cet article une preuve de concept pour l'approche "Étape 1), 2), 3) explicite", sur un problème beaucoup plus simple . Enfin, pour plus d'informations sur GCT, je recommande vivement la revue "Théorie de la complexité géométrique: introduction aux géomètres" de Landsberg.$c(m)$

$$\left(\begin{array}{c}2m\\ m \end{array}\right)-1\ .$$

PS: Je devrais ajouter que mon pessimisme est spécifique à l’hypothèse Valiant qui est l’hypothèse de Riemann sur le terrain. Bien sûr, il ne faut pas jeter le bébé avec l'eau du bain et dénigrer GCT car il n'a jusqu'à présent pas réussi à prouver cette hypothèse. Il y a beaucoup de problèmes plus abordables dans ce domaine où des progrès ont été réalisés et attendus. Voir en particulier l’article susmentionné de Grochow et l’examen de Landsberg.

GCT est un programme de recherche visant à prouver les limites de la théorie de la complexité et défie en quelque sorte un résumé / résumé de type wikipedia en raison de sa grande abstraction, mais de bonnes enquêtes sont disponibles [2] [3] [4]. (et surement Wikipedia est le meilleur endroit pour les entrées wikipedia). Il a été formulé au début des années 2000 par Mulmuley et est à la fois relativement nouveau en théorie de la complexité et très avancé, utilisant et appliquant des mathématiques avancées (géométrie algébrique) qui ne sont pas issues de la théorie TCS / complexité.

Cette approche est considérée comme prometteuse par certains, mais peut-être trop complexe par d'autres autorités, c'est-à-dire qu'elle n'est pas prouvée et par conséquent controversée sur le fait de savoir si elle pourrait surmonter les "obstacles" connus. (en ce sens, il montre certains signes d'un soi-disant "changement de paradigme" kuhnien.) Même Mulmuley propose de ne pas réussir de manière réaliste (en prouvant des séparations de classes de complexité majeures) après des décennies de développement ultérieur. Voici un avis sceptique de Fortnow, une autorité de premier plan dans le domaine de la théorie de la complexité: [1]

Considérez une énorme montagne et vous voulez atteindre le sommet de la montagne. Ketan arrive et dit qu'il va vous apprendre à créer les outils nécessaires pour gravir la montagne. Il faudra un mois d'étude difficile et en réalité, ces outils ne suffisent pas pour gravir la montagne. Ils doivent être améliorés et ces améliorations ne se produiront pas de votre vivant. Mais vous ne voulez pas savoir comment les autres vont gravir les siècles de la montagne?

[1] Comment prouver que NP est différent du blog P Fortnow

[2] Comprendre l'approche Mulmuley-Sohoni de P contre NP Regan

[3] Sur P vs. NP et théorie de la complexité géométrique, Mulmuley.

[4] Le programme GCT face au problème P vs NP, Mulmuley