Algoritma Holografik - Kesetaraan Basa

10

Saya sedang membaca makalah seminal Les Valiant dan saya mengalami kesulitan dengan Proposisi 4.3 di halaman 10 makalah ini.

Aku tidak bisa melihat mengapa kasus bahwa jika ada generator dengan nilai-nilai tertentu untuk dengan dasar { ( a 1 , b 1 ) ... ( a r , b r ) } , maka ada beberapa generator dengan yang sama v a l G nilai untuk basis apa pun { ( x a 1 , y b 1 ) ... ( x a r , y b r )valG{(a1,b1)(ar,br)}valG ( 1 s t k i n d ) atau { ( x b 1 , y a 1 ) ... ( x b r , y a r ) } ( 2 n d k i n d ) untuk setiap x , y F .{(xa1,yb1)(xar,ybr)}1stkind{(xb1,ya1)(xbr,yar)}2ndkindx,yF

Valiant poin alasan di paragraf sebelumnya - yaitu jenis transformasi dapat dicapai dengan menambahkan setiap input atau output simpul tepi berat 1 . The 2 n d jenis transformasi, Valiant mengatakan, dapat dicapai dengan menambahkan input atau output node rantai panjang 2 ditimbang dengan x dan y masing-masing.1st12nd2xy

Saya belum benar-benar memahami pernyataan ini. Mungkin mereka sudah jelas, tetapi saya masih tidak dapat benar-benar melihat mengapa konstruk di atas membantu mencapai nilai dapat direalisasikan dengan satu basis dengan basis baru yang merupakan salah satu tipe di atas.valG

Tolong bantu menerangi mereka untuk saya. Pada catatan yang berbeda, apakah ada beberapa survei bebas tensor untuk algoritma hologaphic yang tersedia online. Sebagian besar dari mereka menggunakan tensor yang, sayangnya, membuatku takut :-(

-Akash terbaik

Akash Kumar
sumber

Jawaban:

8

Tensor (dalam pengertian ini) hanyalah array angka, jadi saya tidak berpikir Anda akan menemukan tensor survey gratis kecuali mereka benar-benar bebas dari perhitungan.

Operasi " " memformalkan operasi perubahan basis dan melampirkan gadget ke setiap simpul keluaran (sebenarnya saya suka menganggap perubahan basis sebagai semacam operasi gadget). Biarkan Γ menjadi kotak korek api generator dengan tanda tangan standar M i 1 i 2i k = u ( Γ ) . Ini array angka 2 k . Tanda tangan dalam basis baru diberikan olehTkΓMi1i2ik=u(Γ)2k

(TkM)i1i2ik:=i1,,ikTi1i1TikikMi1i2ik

di mana adalah matriks dua-dua yang menurunkan basis baru.T

Biarkan menjadi korek api yang dibentuk dengan menambahkan k simpul baru ke Γ , menjadikannya sebagai keluaran baru, dan menghubungkannya ke keluaran lama dengan bobot x . Maka tanda tangan baru adalah C k M di mana C i j adalah matriks ( 0 x 1 0 ) . Jika Anda kemudian melakukan perubahan basis T C - 1 Anda mendapatkan tanda tangan T k M .ΓkΓxCkMCij(0x10)TC1TkM

Colin McQuillan
sumber
Su(Γ)S=S0Tk×S=u(Γ)valG(Γ,x)contoh bahwa ia hanya bermaksud untuk mengekspresikan vektor perfMatch sebagai jumlah koefisien wrt ke basis baru. Saya tidak yakin, karena latar belakang saya yang kurang jelas dengan tensor.
Akash Kumar
CkM
S0(T1)kSTn0,n1,p0,p1
(0,1,1,0,1,0,0,1)x(1,1,1,1 1,1,1,0)C3whereC=(0, 1)t(x=1, 0)tu(Γ)
1
P3P3Zu(P3)=(0,1,0,0,1,0,0,1)(1,0,0,1,0,0,1,0)(C3u(P3))1,2,2=1