Algoritmos holográficos - Equivalência de bases

10

Eu estava analisando o artigo seminal de Les Valiant e tive um momento difícil com a Proposição 4.3 na página 10 do artigo.

Não vejo por que, se existe um gerador com determinados valores para com base , existe algum gerador com os mesmos valores para qualquer base \ {(xa_1, yb_1) \ ldots (xa_r, yb_r) \} ( 1 ^ {st} tipo ) ou \ {(xb_1, ya_1) \ ldots (xb_r, ya_r) \} ( 2 ^ {nd} ) para qualquer x, y \ em F .{ ( a 1 , b 1 ) ( a r , b r ) } v a l G { ( x a 1 , y b 1 ) ( x a r , y b r ) } 1 s t k i n d { ( x b 1 , y umvalG{(a1,b1)(ar,br)}valG{(xa1,yb1)(xar,ybr)}1stkind2 n d k i n d x , y F{(xb1,ya1)(xbr,yar)}2ndkindx,yF

Valiant aponta a razão do parágrafo anterior - ou seja, o tipo de transformação 1st pode ser alcançado anexando a cada nó de entrada ou saída uma extremidade do peso 1 . O 2nd espécie de transformação, Valente diz, pode ser conseguido anexando para nós de entrada ou de saída da cadeia de comprimento 2 ponderadas por x e y , respectivamente.

Não fui realmente capaz de entender essas afirmações. Talvez eles já estejam claros, mas ainda não consigo realmente entender por que a construção acima ajuda a atingir valores valG realizáveis valGcom uma base na nova base, que é um dos tipos acima.

Por favor, ajude a iluminá-los para mim. Em uma nota diferente, existem algumas pesquisas livres de tensoriais para algoritmos holológicos disponíveis on-line. A maioria deles usa tensores que, infelizmente, me assustam :-(

Best -Akash

Akash Kumar
fonte

Respostas:

8

Os tensores (nesse sentido) são apenas matrizes de números, então não acho que você encontrará pesquisas sem tensores, a menos que estejam completamente livres de cálculos.

A operação " " formaliza as operações de mudança de base e anexação de gadgets a cada nó de saída (na verdade, eu gosto de pensar em uma mudança de base como uma espécie de operação de gadget). Seja uma caixa de fósforos de gerador com assinatura padrão . Isso é uma matriz de números. A assinatura em uma nova base é dada por Γ M i 1 i 2i k = u ( Γ ) 2 kTkΓMi1i2ik=u(Γ)2k

(TkM)i1i2ik:=i1,,ikTi1i1TikikMi1i2ik

onde é uma matriz dois por dois descrevendo a nova base.T

Seja a porta de partida formada adicionando novos vértices a , considerando-os como novas saídas e conectando-os às saídas antigas por uma aresta de peso . Então a nova assinatura é onde é a matriz . Se você, em seguida, realizar a alteração da base você começa a assinatura . k Γ x C k M C i j ( 0 x 1 0 ) T C - 1 T k MΓkΓxCkMCij(0x10)TC1TkM

Colin McQuillan
fonte
Desculpe pela resposta tardia, eu estava ocupado hoje. Receio que, devido ao meu entendimento limitado de tensores, ainda não consigo entender você. Eu pensava que a assinatura de uma caixa de fósforos do gerador na nova base, era derivada da assinatura na base antiga pela solução a . Eu pensei que Valiant mencionou em seu exemplo que ele apenas pretendia expressar o vetor perfMatch como a soma dos coeficientes escritos na nova base. Não posso ter certeza, por minha óbvia falta de conhecimento sobre os tensores. u ( Γ ) S = S 0 T k × S = u ( Γ ) v a l G ( Γ , x )Su(Γ)S=S0Tk×S=u(Γ)valG(Γ,x)
Akash Kumar
[continuação] Além disso, eu não sou capaz de seguir o seu exemplo, com . Você poderia elaborar um pouco mais? Obrigado - AkashCkM
Akash Kumar
Fico feliz em tentar elaborar, mas posso estar adicionando uma notação confusa. Você poderia responder isso primeiro: se você adicionar bordas em cada nó de saída, que efeito você acha que isso teria na assinatura? Além disso, que pode ser expresso como - Não me lembro de devem ser os coeficientes reais de em termos de . ( T - 1 )S0T n 0 , n 1 , p 0 , p 1(T1)kSTn0,n1,p0,p1
Colin McQuillan
Vou tentar declarar minha confusão com um exemplo. Considere um gerador cujo caminho seja o comprimento 3, onde todos os 3 nós são o / p. A assinatura deste gerador é . E a assinatura do gadget modificado com 3 novos nós, cada um conectado a um nó o / p na base std, é . Você poderia continuar com este exemplo? Gostaria de ver como atua sobre . Obrigado pela sua paciênciax ( 1 , 1 , 1 , 1 1 , 1 , 1 , 0 ) C 3 w h e r e C = ( 0 , 1 ) t ( x = 1 , 0 ) t u ( Γ(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(Γ)
Akash Kumar
11
Seja um caminho de ordem 3. Chame os vértices x, y, z onde y é o vértice do meio. tem uma correspondência perfeita se Z for {x}, {z} ou {x, y, z}. Então . Com as bordas anexadas, a assinatura é . Tente calcular, por exemplo usando a fórmula acima. P 3Z u ( P 3 ) = ( 0 , 1 , 0 , 0 , 1 , 0 , 0 , 1 ) ( 1 , 0 , 0 , 1 , 0 , 0 , 1 , 0 ) ( C 3 u ( P 3 ) ) 1 , 2 , 2P3P3Zu(P3)=(0,1,0,0,1,0,0,1)(1,0,0,1,0,0,1,0)(C3u(P3))1,2,2=1
Colin McQuillan