Jelaskan interpretasi peringkat-puluhan Gurvits tentang makalah Deolalikar

[Catatan: Saya yakin pertanyaan ini sama sekali tidak bergantung pada benar atau tidaknya makalah Deolalikar.]

Di blog Scott Aaronson, Shtetl Optimized , dalam diskusi tentang upaya Deolalikar baru-baru ini pada P vs NP, Leonid Gurvits membuat komentar berikut :

Saya mencoba memahami / merumuskan kembali pendekatan, dan inilah usaha saya, mungkin sangat minimalis,: distribusi probabilistik diskrit di koran dapat dilihat sebagai tensor, atau polinomial multilinear yang sangat spesial. Asumsi "P = NP" entah bagaimana memberikan batas atas (polinomial?) Pada peringkat tensor. Dan akhirnya, menggunakan hasil probabilistik yang diketahui, ia mendapat batas bawah yang tidak cocok (eksponensial?) Pada peringkat yang sama. Jika saya benar, maka pendekatan ini adalah cara yang sangat cerdas, dalam arti yang baik, untuk mendorong pendekatan aljabar-geometris sebelumnya.

Terlepas dari dugaan / kelemahan yang diketahui dalam bukti Deolalikar, saya penasaran:

Dengan cara apa distribusi yang dibahas dalam makalah Deolalikar dapat dianggap sebagai tensor, dan bagaimana pernyataan hasil-hasilnya (terlepas dari kebenarannya) diterjemahkan ke dalam pernyataan tentang peringkat-tensor?

[Saya sedang membaca sesuatu yang saya pikir sama sekali tidak berhubungan dan kemudian memiliki "momen aha" jadi saya pikir saya sudah menemukan setidaknya sebagian dari jawabannya. Saya tidak yakin apakah ini yang ada dalam pikiran Gurvits, tetapi ini masuk akal bagi saya.]

Distribusi pada n variabel biner dapat dilihat sebagai elemen dari produk tensor (n faktor) ( sebenarnya ruang proyektif yang terkait, tetapi kita akan sampai ke sana). Jika kita memberi label elemen dasar dari setiap salinan oleh danR 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$, maka dasar ruang produk tensor ini diberikan oleh himpunan semua string n-bit. Jika kita memiliki elemen dari produk tensor ini yang koefisiennya berjumlah 1, maka kita dapat menginterpretasikan koefisien dari string n-bit yang diberikan sebagai probabilitas dari string yang terjadi - di mana, distribusi probabilitas! Sekarang, karena kita hanya ingin distribusi probabilitas (koefisien menjumlahkan ke 1) kita dapat menormalkan vektor dalam produk tensor untuk memiliki properti itu. Dengan hanya mempertimbangkan tensor yang dinormalisasi, kami benar-benar hanya mempertimbangkan elemen ruang proyeksi dari produk tensor ini.

Sekarang kita harus menghubungkan tensor-rank ke konsep Deolalikar tentang polylog-parametrizability. Menurut halaman ini oleh Terry Tao, tampaknya gagasan Deolalikar tentang polylog-parametrizability adalah bahwa distribusi dapat "difaktorkan menjadi potensi" sebagai mana pa (i) adalah seperangkat variabel polylog (n), yang didefinisikan sebagai " of i" dan adalah distribusi pada yang hanya bergantung pada variabel induk ini. Selain itu, grafik yang diarahkan orang tua harus asiklik.μ ( x 1 , . . . , x n ) = Π n i = 1 p i ( x i ; x p a ( i )$\mu$$\mu(x_1,...,x_n) = \prod_{i=1}^{n} p_i(x_i ; x_{pa(i)})$$p_i( - ; x_{pa(i)})$$x_i$

Mari kita mulai dengan jenis distribusi yang sangat sederhana. Misalkan memenuhi untuk beberapa distribusi (di mana hanya bergantung pada ). Maka mudah-mudahan jelas bahwa tensor yang sesuai adalah tensor peringkat 1: .$\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)$

Untuk distribusi yang sedikit lebih rumit, misalkan kita ingin mempertimbangkan distribusi seragam pada string di mana (mereka adalah negasi satu sama lain) untuk semua . Dalam interpretasi Tao tentang bahasa Deolalikar, ini akan menjadi distribusi -parametrizable. Maka ini sesuai dengan tensor (perlu dinormalisasi). Jika kita menuliskannya secara penuh, ini mengandung istilah, dan memiliki peringkat tensor paling banyak lebih dari . Namun, berakhir$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$ , ia memiliki tensor-rank 1! Saya percaya fakta terakhir sesuai dengan fakta bahwa faktorisasi dapat dijelaskan oleh angka - untuk setiap pasangan bit yang berdekatan, untuk masing-masing pasangan berdekatan. Secara signifikan lebih kecil dari nyata nomor yang diperlukan dalam teori untuk mu distribusi sewenang-wenang pada kubus Boolean.$O(n)$$O(1)$$O(n)$$2^n$

Saya masih kesulitan merumuskan dua masalah, dan akan sangat menghargai jawaban lebih lanjut tentang mereka:

• Membuat korespondensi yang terakhir tepat
• Menuliskan rumus untuk tensor yang sesuai dengan distribusi parametrizable polylog, dan mendapatkan batas atas pada peringkatnya.