Wyjaśnij interpretację pracy Deolalikara według rangi napinacza Gurvitsa

[Uwaga: uważam, że to pytanie w żaden sposób nie zależy od poprawności lub nieprawidłowości pracy Deolalikar.]

Na blogu Scotta Aaronsona „ Shtetl Optimized” , w dyskusji na temat ostatniej próby Deolalikara przeciwko P vs NP, Leonid Gurvits skomentował :

Próbowałem zrozumieć / przeformułować to podejście i oto moja, być może bardzo minimalistyczna, próba: dyskretne rozkłady probabilistyczne w artykule można traktować jako tensory lub bardzo szczególne wielomianowe wielomiany. Założenia „P = NP” w jakiś sposób dają (wielomian?) Górną granicę rangi tensora. I wreszcie, korzystając ze znanych wyników probabilistycznych, dostaje niepasującą (wykładniczą?) Dolną granicę na tym samym poziomie. Jeśli mam rację, to podejście jest bardzo sprytnym, w pewnym sensie elementarnym, sposobem na popchnięcie poprzednich podejść algebraiczno-geometrycznych.

Pomimo podejrzanych / znanych wad w dowodzie Deolalikara jestem ciekawy:

W jaki sposób rozkłady omówione w pracy Deolalikara można uznać za tensory i w jaki sposób stwierdzenia jego wyników (niezależnie od ich poprawności) przekładają się na stwierdzenia dotyczące rangi tensora?

[Czytałem coś, co uważałem za całkowicie niezwiązane, a potem miałem „aha moment”, więc chyba wymyśliłem przynajmniej część odpowiedzi. Nie jestem pewien, czy to właśnie miał na myśli Gurvits, ale ma to dla mnie sens.]

Rozkład zmiennych binarnych n może być postrzegane jako element iloczynu tensora R 2 ⊗ ⋯ ⊗ R 2 (n czynników) (faktycznie powiązana przestrzeń rzutowa, ale przejdziemy do tego). Jeśli mamy oznaczyć elementy podstawą każdej kopii R 2 przez | 0 ⟩ i | 1 $x_1,...,x_n$$\mathbb{R}^2 \otimes \dotsb \otimes \mathbb{R}^{2}$$\mathbb{R}^2$$|0\rangle$$|1\rangle$, wówczas podstawa tej przestrzeni iloczynu tensora jest podana przez zestaw wszystkich ciągów n-bitowych. Jeśli mamy element tego iloczynu tensorowego, którego współczynniki wynoszą 1, to możemy zinterpretować współczynnik dowolnego ciągu n-bitowego jako prawdopodobieństwo wystąpienia tego ciągu - stąd rozkład prawdopodobieństwa! Teraz, ponieważ chcemy tylko rozkładów prawdopodobieństwa (współczynniki sumujące się do 1), możemy znormalizować dowolny wektor w produkcie tensorowym, który ma tę właściwość. Biorąc pod uwagę tylko znormalizowane tensory, tak naprawdę bierzemy pod uwagę tylko elementy przestrzeni rzutowej tego produktu tensorowego.

Teraz musimy połączyć rangę tensorową z koncepcją Deolalikara dotyczącą parametryzacji polilogu. Według tej stronie Terry Tao, wydaje się, że pojęcie Deolalikar jest z polylog-parametrizability jest to, że dystrybucja może być "uwzględnione potencjału", jak ľ ( x 1 , . . . , X n ) = Π n i = 1 s I ( x i ; x p a ( i ) ) gdzie pa (i) jest zbiorem zmiennych polylog (n), zdefiniowanych jako „rodzice i” oraz$\mu$$\mu(x_1,...,x_n) = \prod_{i=1}^{n} p_i(x_i ; x_{pa(i)})$ to rozkład na x i, który zależy tylko od tych zmiennych nadrzędnych. Ponadto ukierunkowany wykres rodziców powinien być acykliczny.$p_i( - ; x_{pa(i)})$$x_i$

Zacznijmy od bardzo prostego rodzaju dystrybucji. Załóżmy, spełnia μ ( x 1 , . . . , X n ) = Π n i = 1 p ı ( x I ) na jakiś rozkładów P ı (gdzie P i zależy tylko od x I ). To jest oczywiste, z nadzieją, że odpowiednia jest tensor tensor Pozycja 1: ( 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)$

Dla nieco bardziej skomplikowanego rozkładu, załóżmy, że chcemy rozważyć rozkład równomierny na ciągach, gdzie (są one zaprzeczeniem siebie nawzajem) dla wszystkich i . W interpretacji języka Deolalikara przez Tao byłby to rozkład parametryzowalny O ( 1 ) . Następnie Odpowiada tensora ( | 0 ⟩ ⊗ | 1 ⟩ + | 1 ⟩ ⊗ $x_{2i} = 1 - x_{2i+1}$$i$$O(1)$liczbami ( n ) - O (musi być znormalizowany). Jeśli wypiszemy to w całości, zawiera on 2 n / 2 warunki, a więc ma rangę tensorową co najwyżej 2 n / 2 w stosunku do R 2 . Jednak powyżej R 2 ⊗ R 2 ma rangę tensora 1! Uważam, że ten ostatni fakt odpowiada faktowi, że faktoryzację można opisać za pomocą$(|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)$ dla każdej pary sąsiednich bitów, dla każdej z O ( n ) sąsiednich par. Znacząco mniejszy niż 2 n liczb rzeczywistych wymaganych teoretycznie do arbitralnego rozkładu mu na kostce boolowskiej.$O(1)$$O(n)$$2^n$

Nadal mam problemy z sformułowaniem dwóch problemów i chętnie skorzystam z dalszych odpowiedzi na ich temat:

• Doprecyzowanie tej ostatniej korespondencji
• Wypisywanie wzorów dla tensora odpowiadającego rozkładowi parametryzowanemu przez polilog i uzyskanie górnej granicy jego rangi.