Quão difícil é usar a abordagem Mulmuley-Sohoni GCT para mostrar separações de complexidade * conhecidas *?

31

Neste post convidado por Josh Grochow, no blog de complexidade, ele relata um recente workshop dedicado ao GCT, realizado em Princeton em julho. Vários participantes argumentaram que deveríamos usar o GCT para atacar problemas mais fáceis do que vs. , a fim de criar intuição e ver se o método tem potencial.N PPNP

A pergunta que está me incomodando:

É possível usar o GCT para mostrar separações conhecidas como ou ?LP S P A C EPEXPLPSPACE

Faz algo comoLPSPACE

  1. Nem faz sentido no contexto do TCG, ou
  2. É totalmente trivial e desinteressante na estrutura do GCT, ou
  3. Levar a conjecturas tão difíceis quanto vs. ?N PPNP
Mugizi Rwebangira
fonte
Os comentários de Josh nesse post parecem sugerir que é possível formular essa separação na "linguagem GCT", mas isso não é trivial e ninguém chegou a fazê-lo ainda. Mas ainda apreciaria qualquer insight de um especialista.
Mugizi Rwebangira
4
AFAIR, Mulmuley inicia sua apresentação ( video.ias.edu/stream&ref=226 ) com #P vs NC como uma questão mais natural para o GCT. Esta pode ser a primeira intuição para responder à sua pergunta.
Michaël Cadilhac
Obrigado por esse link Michaël. Por alguma razão, o volume é muito baixo para ouvi-lo na área de trabalho do escritório, mas tentarei quando chegar em casa. Embora, de qualquer forma, Josh já tenha dado uma boa resposta.
Mugizi Rwebangira

Respostas:

25

Resposta curta: provavelmente não (1), definitivamente não (2) e possivelmente (3).

Isso é algo em que venho pensando há algum tempo. Primeiro, em certo sentido, o GCT realmente visa limitar as funções de computação, em vez de problemas de decisão. Mas sua pergunta faz todo sentido para as versões de classe de função de , , e .P P S P A C E E X PLPPSPACEEXP

Segundo, provar as versões booleanas - aquelas que conhecemos e amamos, como - é provavelmente incrivelmente difícil em uma abordagem GCT, pois isso exigiria o uso da teoria da representação modular (teoria da representação sobre campos finitos), o que não é bem compreendido em nenhum contexto. FPFEXP

Mas um objetivo razoável pode ser usar o GCT para provar um análogo algébrico do .FPFEXP

Para chegar à sua pergunta: acredito que essas perguntas podem ser formuladas em um contexto de GCT, embora não seja imediatamente óbvio como. Mais ou menos, você precisa de uma função que seja completa para a classe e caracterizada por suas simetrias; bônus extra se a teoria da representação associada à função for fácil de entender, mas essa última geralmente é bastante difícil.

Mesmo quando as perguntas são formuladas em um contexto GCT, não tenho idéia de quão difícil será usar o GCT para provar (análogos algébricos de) etc. As conjecturas teóricas da representação que surgirão nesses contextos provavelmente terão um sabor muito semelhante aos que surgem em vsP N P F E X P F E X PFPFEXPPNPou permanente vs determinante. Pode-se esperar que as provas clássicas desses resultados de separação possam dar uma idéia de como encontrar as "obstruções" teóricas da representação necessárias para uma prova de TCG. No entanto, as provas das declarações mencionadas são todos os teoremas da hierarquia baseados na diagonalização, e não vejo como a diagonalização realmente fornecerá muitas informações sobre a teoria da representação associada a uma função que é completa para o analógico algébrico do , dizer. Por outro lado, ainda não vi como formular o em um contexto de GCT, por isso é um pouco cedo para dizer.FEXPFEXP

Por fim, como mencionei nesse post, Peter Burgisser e Christian Ikenmeyer tentaram provar novamente o limite inferior no limite de fronteira da multiplicação matriz (que foi comprovadamente 7 em 2006 por Joseph Landsberg). Eles foram capazes de mostrar que o nível de fronteira é de pelo menos 6 por uma pesquisa no computador quanto a obstruções no TCG. Atualização em abril de 2013 : desde então, eles conseguiram refazer o resultado de Landsberg usando uma obstrução GCT e mostrar um limite inferior assintótico na multiplicação de matrizes usando tais obstruções. Embora o TCG ainda não tenha reproduzido o limite inferior conhecido na multiplicação de matrizes32×232n22, permite uma pesquisa por computador mais eficiente que a alternativa (o que envolveria as bases de Grobner, que são, no pior dos casos, um tempo duplamente exponencial). Em suas palestras no workshop, Peter e Christian apontaram (corretamente, eu diria) que o que realmente esperamos obter com pequenos exemplos de computação não está provando os limites inferiores conhecidos, mas algumas idéias que nos permitirão usá-los. técnicas para provar novos limites inferiores.

2×23×33×3FPFEXPPNP

Joshua Grochow
fonte
9
FPFEXP
2
Obrigado! Isso foi muito útil. Minha idéia geral (e acho que a dos outros também) foi pensar no que seria um "primeiro passo fácil" neste programa de GCT. Mas parece que não existe realmente (pelo menos até agora). Você mencionou que a abordagem de Grobner Bases tem um tempo de execução duplamente exponencial. Você sabe qual foi o tempo de execução (assintótico) da pesquisa que Burgisser e Ikenmeyer fizeram?
Mugizi Rwebangira
3
Eu acredito que ele ainda era exponencial (que parcialmente explica por que eles não conseguia reproduzir o resultado de Landsberg), mas apenas individualmente exponencial :).
Joshua Grochow 04/04/10
1
@ JoshuaGrochow: Seria útil se você colocasse um banner de atualização no início ou no final da resposta. Na velhice, meus olhos não são mais o que costumavam ser e, ao ler a resposta primeiro, perdi a mudança.
Vijay D
14

Há um novo artigo sobre o arXiv de Joshua Grochow , que mostra como colocar várias técnicas conhecidas de limite inferior na estrutura do GCT e parece que ele responde de alguma forma à sua pergunta.

(Na maioria das vezes, é apenas um comentário, mas ninguém notaria um comentário, por isso estou postando como resposta.)

Unificando e generalizando limites inferiores conhecidos via teoria da complexidade geométrica

Joshua A. Grochow

AC0[p]pelo que é uma unificação natural e uma ampla generalização de resultados conhecidos. Também mostra que a estrutura do TCG é pelo menos tão poderosa quanto os métodos conhecidos e fornece muitas novas provas de conceito de que o TCG pode realmente fornecer limites inferiores assintóticos significativos. Esse novo ponto de vista também abre a possibilidade de interações bidirecionais frutíferas entre resultados anteriores e os novos métodos de TCG; fornecemos várias sugestões concretas de tais interações. Por exemplo, o ponto de vista teórico da representação do GCT fornece naturalmente novas propriedades a serem consideradas na busca de novos limites inferiores. Esse novo ponto de vista também abre a possibilidade de interações bidirecionais frutíferas entre resultados anteriores e os novos métodos de TCG; fornecemos várias sugestões concretas de tais interações. Por exemplo, o ponto de vista teórico da representação do GCT fornece naturalmente novas propriedades a serem consideradas na busca de novos limites inferiores. Esse novo ponto de vista também abre a possibilidade de interações bidirecionais frutíferas entre resultados anteriores e os novos métodos de TCG; fornecemos várias sugestões concretas de tais interações. Por exemplo, o ponto de vista teórico da representação do GCT fornece naturalmente novas propriedades a serem consideradas na busca de novos limites inferiores.

Robin Kothari
fonte