Comment l'approche géométrique de Mulmuley-Sohoni pour produire des bornes inférieures évite-t-elle de produire des preuves naturelles (au sens de Razborov-Rudich)?

La formulation exacte du titre est due à Anand Kulkarni (qui a proposé la création de ce site). Cette question a été posée à titre d'exemple, mais je suis incroyablement curieux. Je connais très peu de choses sur la géométrie algébrique, et en fait, je n'ai aussi qu'une compréhension superficielle de premier cycle des obstacles en jeu dans la question P / poly versus NP (non relativisant, non algébrique, ne sera probablement pas une preuve naturelle) .

Qu'est-ce qui fait que la géométrie algébrique peut contourner ce genre d'obstacles? Est-ce simplement une intuition d'experts sur le terrain ou avons-nous une très bonne raison de croire que l'approche est fondamentalement plus puissante que les approches précédentes? Quels résultats plus faibles cette approche a-t-elle pu atteindre?

[Je vais répondre à la question comme indiqué dans le titre, laissant la litanie d'autres questions sur GCT pour d'autres fils.] Prouver les conjectures qui se posent dans GCT semble comme il utilisera de manière cruciale le fait que les fonctions à l'étude (déterminantes et permanentes, et d'autres polynômes apparentés pour P / poly et NP) sont caractérisés par leurs symétries. Cette nécessité n'est pas un résultat formel, mais une intuition exprimée par plusieurs experts. (Fondamentalement, en l'absence de caractérisation par symétries, il est beaucoup plus difficile de comprendre la géométrie algébrique et la théorie de la représentation qui se posent.)

Cela devrait contourner Razborov-Rudich car très peu de fonctions sont caractérisées par leurs symétries (contournant la condition de grandeur dans la définition des preuves naturelles). Encore une fois, je n'en ai pas vu la preuve, mais c'est une intuition que j'ai entendue exprimée par plusieurs experts.

Maintenant, sur les nombres complexes, il n'est pas clair pour moi qu'il existe un analogue de Razborov-Rudich. Bien que la plupart des GCT se concentrent actuellement sur les nombres complexes, il existe des analogues dans la caractéristique finie (promis dans le prochain article GCT VIII). En caractéristique finie, on pourrait effectivement prouver un énoncé de la forme "Très peu de fonctions sont caractérisées par leurs symétries."

[En réponse au commentaire de Ross Snider, voici une explication de la caractérisation par symétries.]

Tout d'abord, une explication par exemple. Pour l'exemple, définissez une fonction auxiliaire . Si A est une matrice de permutation, alors q ( A ) = 1 et si A est diagonal, alors q ( A ) = d e t ( A ) (produit des entrées diagonales). Supposons maintenant p ( X $q$$A$$q(A)=1$$A$$q(A)=det(A)$$p(X)$ soit un polynôme homogène de degré dans n 2 variables (que nous considérons comme les entires d'une matrice n × n $n$$n^2$$n \times n$$X$). Si a les symétries suivantes:$p$

• (transposer)$p(X) = p(X^t)$
• pour toutes les paires de matrices ( A , B ) telles que A et$p(AXB) = p(X)$$(A,B)$$A$$B$ sont chacune soit des matrices de permutation ou des matrices diagonales et $q(A)q(B) = 1$

alors est un multiple constant de p e r m ( X ) pour toutes les matrices X . On dit donc que le permanent se caractérise par ses symétries.$p(X)$$perm(X)$$X$

Plus généralement, si nous avons un polynôme (homogène) dans m des variables, alors G L m (le groupe de tous les inversible m × m matrices) agit sur f par ( A f ) ( x 1 , . . . , x m ) = f ( A - 1 ( x 1 ) $f(x_1, ..., x_m)$$m$$GL_m$$m \times m$$f$ pour A ∈ G L m (où nous prenons les variables x 1 , . . . , X m comme base pour le m de dimension espace vectoriel sur lequel G L m agit naturellement). Le stabilisateur de f dans G L m est le sous-groupe Stab ( f ) = { A ∈ $(Af)(x_1,...,x_m) = f(A^{-1}(x_1),...,A^{-1}(x_{m}))$$A \in GL_m$$x_1,...,x_m$$m$$GL_m$$f$$GL_m$ . On dit que f est caractérisé par ses symétries si: pour tout polynôme homogène f ′ en m variables de même degré que f , si A f ′ = f ′ pour tout A ∈ Stab ( f ) , alors f ′ est un multiple constant de f .$\text{Stab}(f) = \{ A \in GL_m : Af = f\}$$f$$f'$$m$$f$$Af' = f'$$A \in \text{Stab}(f)$$f'$$f$

La réponse de Joshua Grochow est bonne, mais je pense que cela vaut la peine de faire un commentaire plus général. Le résultat Razborov – Rudich dit que si vous voulez prouver qu'une fonction booléenne n'est pas dans , alors (en supposant que vous croyez leur hypothèse cryptographique), vous devez utiliser une propriété de cette fonction qui n'est pas triviale à calculer ou qui n'est partagé que par un petit nombre d'autres fonctions booléennes. En pratique, il n'est pas facile de trouver des propriétés appropriées; cependant, l'observation Razborov – Rudich n'exclut pas en fait de très nombreux plans généraux d'attaque sur les bornes inférieures du circuit, en l'absence de détails concrets sur la preuve envisagée. Par exemple, supposons que je dise naïvement que mon plan de prouver$P/poly$ impliquait de montrer que S A T ∉ P / p o l y , et que j'avais l'intention d'utiliser le fait que S A T est N P -complet. Ce "plan d'attaque" naïf est presque sans contenu, mais Razborov – Rudich ne l'exclut pas, car lacomplétude N P n'est pas une grande propriété.$NP\not\subseteq P/poly$$SAT\notin P/poly$$SAT$$NP$$NP$

En d'autres termes, Razborov – Rudich ne présente généralement pas beaucoup d'obstacles dans les premiers stades de la planification d'une ligne d'attaque sur les limites inférieures du circuit, tant que vous laissez de la place dans votre plan pour éventuellement utiliser des "propriétés spéciales" de vos fonctions booléennes candidates. Ce n'est que lorsque vous retroussez vos manches et essayez de remplir les détails de l'argument que la barrière de naturalisation commencera à lever la tête pour de bon. Étant donné que GCT est encore à un stade précoce de développement, nous ne devrions pas nous attendre à nous soucier beaucoup de la naturalisation pour le moment (bien que cela vaut bien sûr la peine de vérifier que le programme GCT n'est pas condamné pour des raisons triviales).

Vous pouvez également consulter l'exposition de Ken Regan de GCT, qui comprend quelques remarques sur la barrière de naturalisation.