Expliquer l'interprétation de Gurvits au tenseur de l'article de Deolalikar

[Remarque: je crois que cette question ne dépend en aucune façon de l'exactitude ou de l'inexactitude du document de Deolalikar.]

Sur le blog de Scott Aaronson Shtetl Optimized , dans la discussion sur la récente tentative de Deolalikar sur P vs NP, Leonid Gurvits a fait le commentaire suivant :

J'ai essayé de comprendre / reformuler l'approche, et voici ma tentative, peut-être très minimaliste: les distributions probabilistes discrètes dans l'article peuvent être considérées comme des tenseurs, ou des polynômes multilinéaires très spéciaux. Les hypothèses «P = NP» donnent en quelque sorte une borne supérieure (polynomiale?) Sur le rang du tenseur. Et enfin, en utilisant des résultats probabilistes connus, il obtient une borne inférieure non correspondante (exponentielle?) Sur le même rang. Si j'ai raison, cette approche est un moyen très intelligent, dans un bon sens élémentaire, de pousser les approches géométriques-algébriques précédentes.

Malgré les failles soupçonnées / connues de la preuve de Deolalikar, je suis curieux:

De quelle manière les distributions discutées dans l'article de Deolalikar peuvent-elles être considérées comme des tenseurs, et comment les déclarations de ses résultats (indépendamment de leur exactitude) se traduisent-elles en déclarations sur le rang des tenseurs?

[Je lisais quelque chose que je pensais être totalement indépendant et ensuite j'ai eu un "moment ah" donc je pense que j'ai compris au moins une partie de la réponse. Je ne sais pas si c'est ce que Gurvits avait en tête, mais cela a du sens pour moi.]

Une distribution sur n variables binaires peut être considérée comme un élément du produit tensoriel (n facteurs) ( en fait l'espace projectif associé, mais nous y reviendrons). Si nous étiquetons les éléments de base de chaque copie de par etR 2 ⊗ ⋯ ⊗ R 2 R 2 | 0 ⟩ | 1 $x_1,...,x_n$$\mathbb{R}^2 \otimes \dotsb \otimes \mathbb{R}^{2}$$\mathbb{R}^2$$|0\rangle$$|1\rangle$, alors une base de cet espace de produit tensoriel est donnée par l'ensemble de toutes les chaînes de n bits. Si nous avons un élément de ce produit tensoriel dont les coefficients totalisent 1, alors nous pouvons interpréter le coefficient d'une chaîne de n bits donnée comme la probabilité que cette chaîne se produise - d'où une distribution de probabilité! Maintenant, comme nous ne voulons que des distributions de probabilité (sommation des coefficients à 1), nous pouvons normaliser n'importe quel vecteur du produit tensoriel pour avoir cette propriété. En ne considérant que les tenseurs normalisés, nous ne considérons vraiment que les éléments de l'espace projectif de ce produit tensoriel.

Nous devons maintenant relier le rang du tenseur à la notion de Deolalikar de polylog-parametrizability. Selon cette page de Terry Tao, il semble que la notion de Deolalikar de polylog-parametrizability est que la distribution peut être "factorisée en potentiels" comme où pa (i) est un ensemble de variables polylog (n), définies comme étant les "parents de i" et est une distribution sur qui ne dépend que de ces variables parentes. De plus, le graphe orienté des parents doit être acyclique.um ( x 1 , . . . , x n ) = Π n i = 1 p i ( x i ; x p a ( i ) ) p i ( - ; x p a ( i ) ) x $\mu$$\mu(x_1,...,x_n) = \prod_{i=1}^{n} p_i(x_i ; x_{pa(i)})$$p_i( - ; x_{pa(i)})$$x_i$

Commençons par une distribution très simple. Supposons que satisfait pour certaines distributions (où ne dépend que de ). Il est alors, espérons-le, clair que le tenseur correspondant est le tenseur de rang 1: .um ( x 1 , . . . , x n ) = Π n i = 1 p i ( x i ) p i p i x i ( p 1 ( 0 ) | 0 ⟩ + p 1 ( 1 ) | 1 ⟩ ) ⊗ ⋯ ⊗ ( p n ( 0 ) |$\mu$$\mu(x_1, ..., x_n) = \prod_{i=1}^{n} p_i(x_i)$$p_i$$p_i$$x_i$$(p_1(0)|0\rangle + p_1(1)|1\rangle) \otimes \dotsb \otimes (p_n(0)|0\rangle + p_n(1)|1\rangle)$

Pour une distribution légèrement plus compliquée, supposons que nous voulons considérer la distribution uniforme sur les chaînes où (elles sont la négation de l'autre) pour tout . Dans l'interprétation de Tao de la langue de Deolalikar, ce serait une distribution paramétrable . Cela correspond alors au tenseur (doit être normalisé). Si nous l'écrivons en entier, il contient termes, et a donc un rang de tenseur au plus sur . Cependant,$x_{2i} = 1 - x_{2i+1}$$i$$O(1)$$(|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle) \otimes \dotsb \otimes (|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle)$$2^{n/2}$$2^{n/2}$$\mathbb{R}^2$$\mathbb{R}^2 \otimes \mathbb{R}^2$ , il a le rang de tenseur 1! Je crois que ce dernier fait correspond au fait que la factorisation peut être décrite par des nombres - pour chaque paire de bits adjacents, pour chacune des paires adjacentes. Significativement plus petit que les nombres réels requis en théorie pour une distribution arbitraire mu sur le cube booléen.$O(n)$$O(1)$$O(n)$$2^n$

J'ai toujours du mal à formuler deux problèmes et j'aimerais avoir d'autres réponses à leur sujet:

• Préciser cette dernière correspondance
• Écriture des formules du tenseur correspondant à la distribution paramétrable du polylogue, et obtention d'une borne supérieure sur son rang.