Erklären Sie Gurvits 'Tensor-Rank-Interpretation von Deolalikars Aufsatz

[Anmerkung: Ich glaube, dass diese Frage in keiner Weise von der Richtigkeit oder Unrichtigkeit von Deolalikars Papier abhängt.]

Auf Scott Aaronson Blog Shtetl Optimized , in der Diskussion über Deolalikar jüngsten Versuch P vs NP, machte Leonid Gurvits den folgenden Kommentar :

Ich habe versucht, den Ansatz zu verstehen / neu zu formulieren, und hier ist mein, vielleicht sehr minimalistischer, Versuch: Die diskreten Wahrscheinlichkeitsverteilungen in der Arbeit können als Tensoren oder als sehr spezielle mehrlineare Polynome angesehen werden. Die Annahme "P = NP" ergibt irgendwie eine (polynomische?) Obergrenze für den Tensorrang. Und schließlich erhält er unter Verwendung bekannter probabilistischer Ergebnisse eine nicht übereinstimmende (exponentielle?) Untergrenze für denselben Rang. Wenn ich recht habe, dann ist dieser Ansatz ein sehr geschickter, in gewissem Sinne elementarer Weg, um die vorherigen algebraisch-geometrischen Ansätze voranzutreiben.

Trotz der vermuteten / bekannten Mängel in Deolalikars Beweis bin ich neugierig:

Inwiefern können die in Deolalikars Artikel diskutierten Verteilungen als Tensoren betrachtet werden, und wie lassen sich die Aussagen seiner Ergebnisse (unabhängig von ihrer Richtigkeit) in Aussagen über den Tensorrang umsetzen?

[Ich habe etwas gelesen, von dem ich dachte, es habe nichts damit zu tun und hatte dann einen "Aha-Moment". Ich glaube, ich habe zumindest einen Teil der Antwort herausgefunden. Ich bin mir nicht sicher, ob Gurvits das im Sinn hatte, aber das macht für mich Sinn.]

Eine Verteilung auf n binären Variablen kann als ein Element des Tensorprodukts R 2 ⊗ ⊗ ⊗ R 2 (n Faktoren) angesehen werden (tatsächlich der zugehörige projektive Raum, aber wir werden darauf zurückkommen). Beschriften wir die Basiselemente jeder Kopie von R 2 mit | 0 ⟩ und | 1 $x_1,...,x_n$$\mathbb{R}^2 \otimes \dotsb \otimes \mathbb{R}^{2}$$\mathbb{R}^2$$|0\rangle$$|1\rangle$Dann ist eine Basis dieses Tensorproduktraums durch die Menge aller n-Bit-Strings gegeben. Wenn wir ein Element dieses Tensorprodukts haben, dessen Koeffizienten sich zu 1 summieren, können wir den Koeffizienten einer gegebenen n-Bit-Folge als die Wahrscheinlichkeit interpretieren, mit der diese Folge auftritt - daher eine Wahrscheinlichkeitsverteilung! Da wir nur Wahrscheinlichkeitsverteilungen (Koeffizienten, die zu 1 summieren) wollen, können wir nun jeden Vektor im Tensorprodukt normalisieren, um diese Eigenschaft zu haben. Indem wir nur normalisierte Tensoren betrachten, betrachten wir wirklich nur Elemente des projektiven Raums dieses Tensorprodukts.

Jetzt müssen wir den Tensorrang mit Deolalikars Begriff der Polylog-Parametrisierbarkeit verbinden. Nach dieser Seite von Terry Tao, scheint es , dass Deolalikar Vorstellung von polylog-Parametrisierbarkeit ist , dass die Verteilung als "in Potentiale berücksichtigt" werden kann μ ( x 1 , . . . , X n ) = Π n i = 1 p i ( x i ; x p a ( i ) ) wobei pa (i) eine Menge von Polylog (n) -Variablen ist, definiert als "Eltern von i" und$\mu$$\mu(x_1,...,x_n) = \prod_{i=1}^{n} p_i(x_i ; x_{pa(i)})$ ist eine Verteilung von x i , die nur von diesen übergeordneten Variablen abhängt. Darüber hinaus sollte der gerichtete Graph der Eltern azyklisch sein.$p_i( - ; x_{pa(i)})$$x_i$

Beginnen wir mit einer sehr einfachen Art der Verteilung. Angenommen erfüllt μ ( x 1 , . . . , X n ) = Π n i = 1 p i ( x i ) für einige Verteilungen p i (wobei p i hängt nur von x i ). Dann ist es hoffentlich klar , dass die entsprechende Tensor der Rang 1 Tensor ist: ( p 1 ( 0 ) | 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)$

Nehmen wir für eine etwas kompliziertere Verteilung an, wir wollen die gleichmäßige Verteilung über die Strings betrachten, wobei (sie sind die Negation des jeweils anderen) für alle i . In Taos Interpretation von Deolalikars Sprache wäre dies eine O ( 1 ) -parametrierbare Verteilung. Dann Dies entspricht dem Tensor ( | 0 ⟩ & xotime ; | 1 ⟩ + | 1 ⟩ & xotime ; | 0 ⟩ ) & xotime ; ⋯ & $x_{2i} = 1 - x_{2i+1}$$i$$O(1)$ (Bedarf normalisiert werden). Wenn wir dies vollständig ausschreiben, enthält es 2 n / 2 Terme und hat daher einen Tensorrang von höchstens 2 n / 2 über R 2 . Über R 2 ⊗ R 2 hat es jedoch Tensorrang 1! Ich glaube, die letztere Tatsache entspricht der Tatsache, dass die Faktorisierung durch O ( n ) Zahlen -$(|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$$O(n)$ für jedes Paar benachbarter Bits für jedes von O ( n ) benachbarten Paaren. Deutlich kleiner als dietheoretisch erforderlichen 2 n reellen Zahlen für eine beliebige Verteilung mu auf dem Booleschen Würfel.$O(1)$$O(n)$$2^n$

Ich habe immer noch Probleme bei der Formulierung von zwei Problemen und würde mich über weitere Antworten freuen:

• Präzisierung der letztgenannten Korrespondenz
• Schreibe die Formeln für den Tensor auf, die der durch Polylog parametrisierbaren Verteilung entsprechen, und erhalte eine Obergrenze für seinen Rang.