Explicar a interpretação de Gurvits no tensor do artigo de Deolalikar

[Nota: Eu acredito que esta questão não depende da correção ou incorreta do artigo de Deolalikar.]

No blog de Scott Aaronson, Shtetl Optimized , na discussão sobre a recente tentativa de Deolalikar em P vs NP, Leonid Gurvits fez o seguinte comentário :

Tentei entender / reformular a abordagem, e aqui está a minha tentativa, talvez muito minimalista: as distribuições probabilísticas discretas no artigo podem ser vistas como tensores ou polinômios multilineares muito especiais. As suposições “P = NP” de alguma forma fornecem um limite superior (polinomial?) No ranking do tensor. E, finalmente, usando resultados probabilísticos conhecidos, ele obtém um limite inferior não correspondente (exponencial?) Na mesma classificação. Se estou certo, essa abordagem é uma maneira muito inteligente, em um bom sentido elementar, de promover as abordagens algébricas-geométricas anteriores.

Apesar das falhas suspeitas / conhecidas na prova de Deolalikar, estou curioso:

De que maneira as distribuições discutidas no artigo de Deolalikar podem ser consideradas como tensores e como as declarações de seus resultados (independentemente de sua exatidão) se traduzem em declarações sobre a classificação dos tensores?

[Eu estava lendo algo que achava totalmente não relacionado e depois tive um "momento aha", então acho que descobri pelo menos parte da resposta. Não tenho certeza se é isso que Gurvits tinha em mente, mas isso faz sentido para mim.]

A distribuição de variáveis n binários pode ser visto como um elemento do produto tensor R 2 ⊗ ⋯ ⊗ R 2 (n fatores) (na verdade, o espaço projetivo associado, mas nós vamos chegar a isso). Se rotular os elementos da base de cada cópia de R 2 por | 0 ⟩ e | 1 $x_1,...,x_n$$\mathbb{R}^2 \otimes \dotsb \otimes \mathbb{R}^{2}$$\mathbb{R}^2$$|0\rangle$$|1\rangle$, uma base desse espaço do produto tensorial é fornecida pelo conjunto de todas as seqüências de n bits. Se temos um elemento desse produto tensorial cujos coeficientes somam 1, então podemos interpretar o coeficiente de qualquer cadeia de n bits dada como a probabilidade de ocorrência dessa cadeia - daí, uma distribuição de probabilidade! Agora, como queremos apenas distribuições de probabilidade (coeficientes somando 1), podemos normalizar qualquer vetor no produto tensorial para ter essa propriedade. Considerando apenas os tensores normalizados, estamos realmente considerando apenas elementos do espaço projetivo desse produto tensorial.

Agora temos que conectar a classificação do tensor à noção de Deolalikar de polilog-parametrizabilidade. De acordo com esta página por Terry Tao, parece que a noção de polylog-parametrizability de Deolalikar é que a distribuição pode ser "tidos em conta potenciais" como μ ( x 1 , . . . , X n ) = Π n i = 1 p i ( x i ; x p a ( i ) ) onde pa (i) é um conjunto de variáveis ​​polylog (n), definidas como os "pais de i" e$\mu$$\mu(x_1,...,x_n) = \prod_{i=1}^{n} p_i(x_i ; x_{pa(i)})$ é uma distribuição em x i que depende apenas dessas variáveis ​​pai. Além disso, o gráfico direcionado dos pais deve ser acíclico.$p_i( - ; x_{pa(i)})$$x_i$

$\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)$

$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$$O(n)$$O(1)$$O(n)$$2^n$

Ainda estou com problemas para formular dois problemas e gostaria de receber mais respostas:

• Tornando a última correspondência precisa
• Escreva as fórmulas para o tensor correspondente à distribuição polilog parametrizável e obtenha um limite superior em sua classificação.