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 P
A pergunta que está me incomodando:
É possível usar o GCT para mostrar separações conhecidas como ou ?L ≠ P S P A C E
Faz algo como
- Nem faz sentido no contexto do TCG, ou
- É totalmente trivial e desinteressante na estrutura do GCT, ou
- Levar a conjecturas tão difíceis quanto vs. ?N P
cc.complexity-theory
gct
Mugizi Rwebangira
fonte
fonte
Respostas:
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 PL P PSPACE EXP
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.FP≠FEXP
Mas um objetivo razoável pode ser usar o GCT para provar um análogo algébrico do .FP≠FEXP
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 PFP≠FEXP P NP ou 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.FEXP FEXP
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.2×2 32n2−2
Embora o TCG ainda não tenha reproduzido o limite inferior conhecido na multiplicação de matrizes3, 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.fonte
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.)
fonte