Abordagem cohomológica da complexidade booleana

33

Alguns anos atrás, Joel Friedman havia algum trabalho relacionado aos limites inferiores do circuito à cohomologia de Grothendieck (veja artigos: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ) Essa linha de pensamento trouxe novas idéias para a complexidade booleana ou continua sendo uma curiosidade matemática?

Marcin Kotowski
fonte
4
Estou muito curioso para ver a resposta para isso. Naturalmente, o mais fácil seria enviar e-mail Joel Friedman :)
Suresh Venkat

Respostas:

28

Eu me correspondi com Joel Friedman cerca de 3 anos atrás sobre este tópico. Na época, ele disse que sua abordagem não levara a novas idéias significativas sobre a teoria da complexidade, embora ainda achasse que era uma abordagem promissora.

Basicamente, Friedman tenta reformular os problemas de complexidade do circuito na linguagem das polias em uma topologia de Grothendieck. A esperança é que esse processo permita que a intuição geométrica seja aplicada ao problema de encontrar limites inferiores do circuito. Embora valha a pena verificar para ver se esse caminho leva a algum lugar, há razões heurísticas para ser cético. A intuição geométrica funciona melhor no contexto de variedades suaves, ou coisas que são suficientemente semelhantes às variedades suaves que a intuição não se decompõe totalmente. Em outras palavras, você precisa de alguma estrutura para que a intuição geométrica ganhe um ponto de apoio. Mas os limites mais baixos do circuito, por sua própria natureza, devem confrontar cálculos arbitrários, que são difíceis de analisar precisamente porque parecem ser tão sem estrutura. Friedman admite logo de cara que as topologias de Grothendieck que considera são altamente combinatórias e muito distantes dos objetos usuais de estudo em geometria algébrica.

Como um comentário secundário, eu diria que é importante não ficar muito animado com uma ideia apenas porque ela usa máquinas desconhecidas e de alta potência. A maquinaria pode ser muito eficaz na resolução dos problemas para os quais foi projetada, mas, para ser útil no ataque a um problema difícil conhecido em outro domínio, é preciso haver algum argumento convincente sobre o motivo da maquinaria estrangeira estar bem adaptada para abordar as questões fundamentais. obstáculo no problema de interesse.

Timothy Chow
fonte
4
É claro que os esforços de Mulmuley seguem linhas "semelhantes" no sentido de usar "estruturas suaves", mas ele está olhando para problemas que admitem bons invariantes geométricos para começar.
Suresh Venkat
2
@Suresh: Você está certo que a abordagem de Mulmuley-Sohoni é diferente, mas o problema fundamental de lidar com uma computação arbitrária ainda está à espreita em segundo plano, por isso é justo perguntar exatamente como alguém espera lidar com ela. No momento, acho que ninguém sabe realmente, e é por isso que o pessoal do GCT não promete promessas espetaculares tão cedo.
Timóteo Chow
de fato. é interessante ver um papel STOC de 2011 que usos GCT para limites multiplicação de matrizes (e Ketan havia mencionado esse resultado em seu tutorial em FOCS)
Suresh Venkat
1
@Suresh: Se você está falando sobre o artigo de Buergisser / Ikenmeyer, acho que diz muito mais sobre os limites da abordagem GCT do que sobre como provar limites mais baixos.
5501
1
@ Neel, eu não tenho uma resposta, mas me pergunto se isso pode merecer uma pergunta própria.
Suresh Venkat
16

Eu acho que Timothy Chow está certo. Eu tenho minha própria lista de idéias pessoais que envolvem variedades "suaves" ou conceitos como contar componentes ou monômios conectados que acompanham os poucos degraus inferiores da "escada da cohomologia" - todos eles demonstrados como não sendo predicados pela dureza por ( variações) na construção de Mayr-Meyer mostrando a completude EXPSPACE de vários problemas relacionados ao TCG. Meu único riff em seu último parágrafo é que acho que é necessário algum tipo de maquinaria de alta potência ...!

Kenneth W. Regan
fonte