Explicação no estilo Wikipedia da Teoria da Complexidade Geométrica

Alguém pode fornecer uma explicação concisa da abordagem GCT de Mulmuley, compreensível por não especialistas? Uma explicação que seria adequada para uma página da Wikipedia sobre o tópico (que é um esboço no momento).

Motivação: estou "co-lendo" o livro Quantum Computing, de Scott Aaronson, desde Demócrito, com um amigo meu que é pesquisador em teoria das cordas. No prefácio do livro, Aaronson chama o GCT de "teoria das cordas da ciência da computação". Sendo um teórico das cordas, meu amigo ficou entusiasmado com essa afirmação e me perguntou o que é o GCT. Nesse ponto, vergonhosamente percebi que não tinha uma resposta pronta para a Wikipedia para sua pergunta.

Não sei exatamente qual é o nível adequado para o artigo da Wikipedia (artigos diferentes parecem direcionados a diferentes níveis de conhecimento) ou exatamente o que você está procurando. Então, aqui está uma tentativa, mas estou aberto a comentários.

A teoria da complexidade geométrica propõe estudar a complexidade computacional das funções computacionais (digamos, polinômios), explorando as simetrias inerentes à complexidade e quaisquer simetrias adicionais das funções que estão sendo estudadas.

Como em muitas abordagens anteriores, o objetivo final é separar duas classes de complexidade , mostrando que existe um polinômio que assume funções como entradas (por exemplo, , por seus vetores de coeficiente), de forma que desaparece em todas as funções mas não desaparece em alguma função . pfpf∈ C e a s y g h a r d ∈ C h a r $\mathcal{C}_{easy}, \mathcal{C}_{hard}$$p$$f$$p$$f \in \mathcal{C}_{easy}$$g_{hard} \in \mathcal{C}_{hard}$

A primeira idéia-chave (cf. [GCT1, GCT2]) é usar simetrias para organizar não as próprias funções, mas para organizar as propriedades ( algebro-geométricas ) dessas funções, capturadas por polinômios como acima. Isso permite o uso da teoria da representação na tentativa de encontrar uma . Idéias semelhantes relacionadas à teoria das representações e à geometria algébrica já haviam sido usadas na geometria algébrica antes, mas para o meu conhecimento nunca dessa maneira.$p$$p$

A segunda ideia-chave (cf. [GCT6]) é encontrar algoritmos combinatórios (e em tempo polinomial) para os problemas teóricos da representação resultantes e depois fazer engenharia reversa desses algoritmos para mostrar que esse existe. Isso pode ser tomado no espírito de usar a Programação Linear (um algoritmo) para provar certas declarações puramente combinatórias.$p$

De fato, [GCT6] sugere reduzir os problemas teóricos da representação acima para problemas de Programação Inteira , mostrando então que os IPs resultantes são resolvidos por seus relaxamentos de LPs e, finalmente, fornecendo algoritmos combinatórios para os LPs resultantes. As conjecturas em [GCT6] são motivadas por resultados conhecidos de engenharia reversa para os coeficientes de Littlewood-Richardson, um problema análogo, porém mais fácil, na teoria das representações. No caso dos coeficientes de RL, a regra combinatória de Littlewood-Richardson veio em primeiro lugar. Mais tarde, Berenstein e Zelevinsky [BZ] e Knutson e Tao [KT] (veja [KT2] para uma visão geral amigável) forneceram um IP para os coeficientes de RL. Knutson e Tao também provaram a conjectura de saturação, o que implica que o PI é resolvido por seu relaxamento de LP (cf. [GCT3, BI]).

Os resultados de [GCT5] mostram que a des aleatorização explícita do lema de normalização de Noether é essencialmente equivalente ao notório problema em aberto na teoria da complexidade da des randomização em caixa preta dos testes de identidade polinomial . Basicamente, como isso se encaixa no programa maior é que encontrar uma base explícita para as funções que (não) desaparecem em (nesse caso, a classe para a qual o determinante está completo) pode ser usado para derivar uma regra combinatória para o problema desejado na teoria das representações, como aconteceu em outras configurações na geometria algébrica. Um passo intermediário aqui seria encontrar uma base para os que (não) desaparecem sobre a normalização dasC e uma s y p C e uma s $p$$\mathcal{C}_{easy}$$p$$\mathcal{C}_{easy}$ , que é a construção de uma variedade algébrica mais agradável - em outras palavras, para derandomizar o Lemma de Normalização de Noether para DET.

Exemplos de simetrias de complexidade e funções

Por exemplo, a complexidade de uma função - para a maioria das noções naturais de complexidade - permanece inalterada se permutarmos as variáveis por alguma permutação . Assim, permutações são simetrias da própria complexidade. Para algumas noções de complexidade (como na complexidade do circuito algébrico) todas as mudanças lineares invertíveis das variáveis ​​são simetrias.f ( x π ( 1 ) , … , x π ( n ) ) $f(x_1, \dotsc, x_n)$$f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$$\pi$

Funções individuais podem ter simetrias adicionais. Por exemplo, o determinante possui as simetrias para todas as matrizes modo que . (Pelo pouco que aprendi sobre isso, concluo que isso é análogo ao fenômeno da quebra espontânea de simetria na física.)$\det(X)$$\det(AXB) = \det(X^{T}) = \det(X)$$A,B$$\det(AB) = 1$

Algum progresso recente [esta seção definitivamente incompleta e mais técnica, mas uma conta completa levaria dezenas de páginas ... Eu só queria destacar algum progresso recente]

Burgisser e Ikenmeyer [BI2] mostraram um limite inferior de na multiplicação de matrizes após o programa GCT, tanto quanto usavam representações com multiplicidades zero vs diferentes de zero. Landsberg e Ottaviani [LO] deram o limite inferior mais conhecido de essencialmente no posto fronteiriço da multiplicação de matrizes usando a teoria das representações para organizar propriedades algébricas, mas não usando multiplicidades de representações nem regras combinatórias.$\frac{3}{2}n^2$$2n^2$

O próximo problema após os coeficientes de Littlewood-Richardson são os coeficientes de Kronecker . Eles aparecem tanto em uma série de problemas que se suspeita que eventualmente atinjam os problemas teóricos da representação que surgem no TCG e mais diretamente como limites nas multiplicidades da abordagem do TCG para a multiplicação de matrizes e permanente versus determinante. Encontrar uma regra combinatória para os coeficientes de Kronecker é um problema aberto de longa data na teoria das representações; Blasiak [B] recentemente deu uma regra combinatória para os coeficientes de Kronecker com uma forma de gancho.

Kumar [K] mostrou que certas representações aparecem no anel de coordenadas do determinante com multiplicidade diferente de zero, assumindo a conjectura do quadrado latino da coluna (cf. Huang-Rota e Alon-Tarsi; essa conjectura também, talvez não por coincidência, aparece em [BI2 ]). Portanto, essas representações não podem ser usadas para separar permanente de determinante com base em multiplicidades zero versus diferente de zero, embora ainda seja possível usá-las para separar permanente de determinante por uma desigualdade mais geral entre multiplicidades.

Referências [B] J. Blasiak. Coeficientes Kronecker para um formato de gancho. arXiv: 1209.2018, 2012.

[BI] P. Burgisser e C. Ikenmeyer. Um algoritmo de fluxo máximo para positividade dos coeficientes de Littlewood-Richardson. FPSAC 2009.

[BI2] P. Burgisser e C. Ikenmeyer. Limites inferiores explícitos via teoria da complexidade geométrica. arXiv: 1210.8368, 2012.

[BZ] AD Berenstein e AV Zelevinsky. Multiplicidades triplas para e o espectro da álgebra externa da representação adjunta. $\mathfrak{sl}(r+1)$J. Algebraic Combin. 1 (1992), n. 1, 7-22.

[GCT1] KD Mulmuley e M. Sohoni. Teoria da Complexidade Geométrica I: Uma Abordagem de P vs. NP e Problemas Relacionados. SIAM J. Comput. 31 (2), 496-526, 2001.

[GCT2] KD Mulmuley e M. Sohoni. Teoria da Complexidade Geométrica II: Rumo a Obstruções Explícitas para Casamentos entre Variedades de Classe. SIAM J. Comput., 38 (3), 1175-1206, 2008.

[GCT3] KD Mulmuley, H. Narayanan e M. Sohoni. Teoria da complexidade geométrica III: na decisão de não-fuga de um coeficiente de Littlewood-Richardson. J. Algebraic Combin. 36 (2012), n. 1, 103-110.

[GCT5] KD Mulmuley. Teoria da Complexidade Geométrica V: Equivalência entre a des randomização da caixa preta do teste de identidade polinomial e a des randomização do Lema de Normalização de Noether. FOCS 2012, também arXiv: 1209.5993.

[GCT6] KD Mulmuley. Teoria da Complexidade Geométrica VI: o flip via positividade. , Relatório Técnico, departamento de Ciência da Computação, Universidade de Chicago, janeiro de 2011.

[K] S. Kumar. Um estudo das representações apoiadas pelo fechamento da órbita do determinante. arXiv: 1109.5996, 2011.

JM Landsberg e G. Ottaviani. Novos limites inferiores para a classificação de borda da multiplicação de matrizes. arXiv: 1112.6007, 2011.

A. Knutson e T. Tao. O modelo de favo de mel dos produtos tensores . I. Prova da conjectura de saturação. $\text{GL}_n(\mathbb{C})$J. Amer. Matemática. Soc. 12 (1999), n. 4, 1055-1090.

[KT2] A. Knutson e T. Tao. Favos de mel e somas de matrizes hermitianas. Avisos Amer. Matemática. Soc. 48 (2001), n. 2, 175-186.

Recentemente, respondi a uma pergunta relacionada no Mathoverflow https://mathoverflow.net/questions/277408/what-are-the-current-breakthroughs-of-geometric-complexity-theory

Como este site é talvez um local melhor, deixe-me repetir a resposta abaixo. As referências a Joseph ou Timothy são sobre os outros posts para essa pergunta do MO.

---

Seja uma matriz genérica e o grau polinomial homogêneo dado por o determinante. Seja que leva o permanente de uma submatriz multiplica pela forma linear favorita de alguém para criar outro polinômio homogêneo de grau (também é possível usar a entrada vez de ). Essa modificação é chamada de preenchimento . Em seguida, defina o número $X=(X_{ij})_{1\le i,j\le n}$$n\times n$$F_1(X)={\rm det}(X)$$n$

$$F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right]$$ $m\times m$$n$$X_{11}$$X_{nn}$ $$c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \}$$ que é atuando no espaço afim da dimensão onde vive e são fechamentos de órbitas de Zariski. A grande conjectura na área ou a Hipótese de Valiant (uma versão complexa de ) é que cresce mais rápido que qualquer polinômio em .$G$$GL(n^2)$$n^2$$X$$\overline{G\cdot F_i}$${\rm P}\neq{\rm NP}$$c(m)$$m$

Agora, se , então um possui um mapa de equivalentes a entre as partes do grau dos anéis de coordenadas desses fechamentos de órbita. Portanto, o jogo é tentar mostrar que isso não acontece, por insuficientemente grande em relação a , comprovando a existência de uma obstrução à multiplicidade , ou seja, uma representação irredutível para a qual as multiplicidades satisfazem $\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$$G$

$$\mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d$$ $d$$n$$m$$\lambda$ $${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)$$ ou no nível de ideais $${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ .$$

Uma abordagem otimista é tentar mostrar que existem obstruções de ocorrência , ou seja, são tais que e . Essa esperança foi esmagada no trabalho de Bürgisser, Ikenmeyer e Panova mencionado por Timothy. No entanto, a possibilidade de obstruções à multiplicidade ainda está aberta.$\lambda$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$

Penso que a abordagem de Mulmuley é tentar provar a existência de tais obstáculos de multiplicidade, aproveitando todas as ferramentas disponíveis na teoria da representação para o cálculo dessas multiplicidades. Pessoalmente, nunca fui fã dessa abordagem. Tendo estudado a teoria invariante do século XIX em alguma profundidade, parece-me mais natural abordar o problema da separação de órbitas usando as ferramentas explícitas daquela época. Este artigo de Gorchow também parece apontar em uma direção semelhante (suspeito que o terceiro artigo mencionado por Joseph esteja na mesma linha). Na linguagem clássica (veja Turnbull ou Littlewood ), é preciso construir explicitamente um concomitante misto que desaparece emF $F_1$mas não no . Também é preciso fazer isso infinitamente (em ) para estabelecer a propriedade de crescimento superpolinomial. Tal concomitante é o mesmo que um mapa específico de derivativo do seu modelo favorito para a representação irredutível para a álgebra polinomial nas variáveis (Grochow chama isso de módulo de separação ). Teóricos invariantes do século XIX tinham dois métodos para gerar tais objetos: teoria da eliminação e álgebra diagramática .$F_2$$m$$G$$\lambda$$n^2$$X$

Um exemplo muito pequeno em que e são formas binárias sob a ação de (veja esta pergunta MO ) é: e Um concomitante separador (aqui de fato uma covariante) é o Hessiano de um quártico binário genérico Ele desaparece (identicamente em ) para mas não para$F_1$$F_2$$G=SL(2)$

$$F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4$$ $$F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ .$$ $F$ $$H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ .$$ $x,y$$F=F_1$$F=F_2$. Nesse caso, o Hessiano pode ser visto como um mapa equivariante do irredutível dado pelo segundo poder simétrico (da representação bidimensional fundamental) no anel de coordenadas do espaço afim dos quadráticos binários.

Portanto, um possível "plano" super-otimista para o GCT envolve a seguinte sequência de etapas.

1) Encontre uma maneira de gerar toneladas de concomitantes.

2) Identifique alguns candidatos explícitos para o desaparecimento em e prove essa propriedade.$F_1$

3) Mostre que eles não desaparecem em .$F_2$

O passo 1) é, em princípio, resolvido pelo Primeiro Teorema Fundamental para mas existe uma incompatibilidade: o determinante é um objeto natural na teoria invariante para (atuando em linhas e colunas) em vez de . Poder-se-ia tentar consertar a incompatibilidade expressando o alicerce básico da teoria invariante de em termos de um para (veja esta questão do MO para um problema de redução semelhante de para ).$GL(n^2)$$GL(n)\times GL(n)$$GL(n^2)$$GL(n^2)$$GL(n)\times GL(n)$$SL(n(n+1)/2)$$SL(n)$

Adivinhar os candidatos certos para a Etapa 2) me parece difícil. Saber de antemão que algumas multiplicidades são diferentes de zero definitivamente ajudariam. Embora, seja possível procrastinar e adiar a prova de desaparecimento não idêntico do concomitante à Etapa 3), que deve mostrar mais do que isso de qualquer maneira. Se alguém tem esses candidatos certos, mostrar que desaparece em pode ser fácil com argumentos que se poderia chamar de princípio de exclusão de Pauli (contratação de simetrizações com antissimetrizações), propriedade de número cromático alto ou simplesmente "falta de espaço".${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$$F_1$

No entanto, acho que a parte mais difícil é a Etapa 3). Por exemplo, em meu artigo "16.051 fórmulas para o invariante triplo cúbico de Ottaviani" com Ikenmeyer e Royle, o palpite foi feito por pesquisa no computador, mas com o candidato certo em mãos, o desaparecimento de foi relativamente fácil de explicar (é um pouco exemplo bonito de número cromático devido às propriedades globais do gráfico, e não a um grande clique). O análogo da Etapa 3) em nosso artigo foi feito pelo cálculo por computador de força bruta e ainda não temos idéia de por que isso é verdade. O problema paradigmático relacionado à Etapa 3) é a conjectura de Alon-Tarsi (veja esta questão do MO e esta$F_1$também). Na minha opinião, é preciso avançar nesse tipo de questão (o Teorema das Quatro Cores também é desse tipo, através de uma redução devido a Kauffman e Bar-Natan) antes da Conjectura de Valiant.

Uma vez que a pergunta é sobre avanços no GCT. Acho que este artigo de Landsberg e Ressayre também merece alguma atenção, pois sugere que uma estimativa razoável do valor exato de está Observe que uma prova de conceito para a abordagem explícita "Etapa 1), 2), 3)", sobre um problema muito mais simples, foi dada por Bürgisser e Ikenmeyer neste artigo . Finalmente, para obter mais informações sobre GCT, recomendo vivamente a revisão "Teoria da complexidade geométrica: uma introdução para geômetros", de Landsberg.$c(m)$

$$\left(\begin{array}{c}2m\\ m \end{array}\right)-1\ .$$

PS: Devo acrescentar que meu pessimismo é específico da Hipótese Valiant, que é a Hipótese de Riemann no campo. Evidentemente, não se deve jogar o bebê na água do banho e denegrir o TCG porque até agora não conseguiu provar essa conjectura. Existem muitos problemas mais acessíveis nessa área em que foram feitos progressos e é esperado mais progresso. Veja em particular o artigo acima mencionado de Grochow e a revisão de Landsberg.

O GCT é um programa de pesquisa para comprovar os limites da teoria da complexidade e, de certa forma, desafia um resumo / resumo no estilo da Wikipédia devido à sua pesada abstração, mas para a multidão do TCS estão disponíveis boas pesquisas. [2] [3] [4] (e certamente a Wikipedia é o melhor lugar para entradas da Wikipedia). foi formulado no início dos anos 2000 por Mulmuley e é relativamente novo na teoria da complexidade e muito avançado, usando e aplicando matemática avançada (geometria algébrica) que não se originou na teoria da complexidade / TCS.

a abordagem é considerada promissora por algumas autoridades, mas possivelmente muito complexa por outras autoridades, ou seja, não está comprovada e, portanto, controversa se poderia superar as "barreiras" conhecidas. (nesse sentido, exibe alguns sinais da chamada "mudança de paradigma" kuhniana). Até Mulmuley propõe que, realisticamente, talvez não seja bem-sucedido (provando grandes separações de classes de complexidade) após décadas de desenvolvimento. aqui está uma opinião cética de Fortnow, uma autoridade líder no campo da teoria da complexidade: [1]

Considere uma montanha enorme e você quer alcançar o topo da montanha. Ketan aparece e diz que o ensinará a criar as ferramentas necessárias para escalar a montanha. Vai levar um mês duro de estudo e, na verdade, essas ferramentas não são boas o suficiente para escalar a montanha. Eles precisam ser aprimorados e essas melhorias não acontecerão durante a sua vida. Mas você não quer aprender como os outros escalarão a montanha daqui a séculos?

[1] Como provar NP diferente do blog P Fortnow

[2] Compreendendo a abordagem de Mulmuley-Sohoni para P vs. NP Regan

[3] Sobre P vs. NP e teoria da complexidade geométrica Mulmuley

[4] O programa GCT para o problema P vs. NP Mulmuley