Artigos sobre a relação entre complexidade computacional e geometria / topologia algébrica?

22

Fiquei me perguntando quais papéis eu deveria ler para entender esta pergunta

Uma conexão inesperada com outras áreas da matemática, como geometria algébrica ou cohomologia superior. Talvez até uma área da matemática ainda não desenvolvida. Talvez alguém desenvolva uma direção totalmente nova para a matemática, a fim de lidar com a questão P versus NP. - De Fortnow 2002

Outro fraseado da pergunta seria "Quais documentos devo ler para criar uma conexão da complexidade computacional à geometria / topologia algébrica?"

Já examinei a Teoria da Complexidade Geométrica . Também trabalhos em Computação Quântica Topológica, que já li em documentos suficientes que já estou familiarizado com o campo. Estou faltando alguma coisa?

cc.complexity-theory reference-request gct algebraic-topology Joshua Herman
fonte
1
Posso sugerir uma alteração no título? Algo como "Artigos sobre relação entre Complexidade computacional e geometria / topologia algébrica".
Kaveh
Você poderia elaborar sua pergunta um pouco? Eu acho que todo mundo sentiria falta de algo nessa linha, se essa linha for verdadeira, pois ele está falando de "incógnitas". Acho que a resposta do professor Suresh abaixo, nos limites inferiores, é uma boa referência.
vs
2
Você também pode querer olhar para esta questão relacionada: cstheory.stackexchange.com/questions/2898/...
Martin Schwarz
1
Eu também achei este papel cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf
Joshua Herman

Respostas:

10
vs
fonte
Esse é um exemplo explícito da co-homologia da etale? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf
Joshua Herman
Por favor, consulte aqui. www-math.mit.edu/~kedlaya/18.787/intro.pdf
vs
1
O trabalho do Sudão e Guruswami é principalmente dedicado à decodificação de listas (que também se refere aos códigos AG) - tópico que surgiu no final dos anos 90 e foi fortemente desenvolvido nos anos 2000. O método de geometria algébrica apareceu aos 80 s em artigos de Goppa, e foi desenvolvido por Tsfasman e Vladutc e muitos outros aos 90 s. Pessoalmente eu gostaria de sugerir o papel: Hoholdt, van Lint, Pellikaan, códigos de geometria algébrica, 1998.
Artem Pelenitsyn
1
Quanto à AG computacional, eu sugeriria livros de Cox - Little - O'Shea e Schenck, mas esse tópico é um pouco irrelevante para a "conexão da complexidade computacional à geometria algébrica" ​​solicitada por Joshua.
Artem Pelenitsyn
4

No Slide 26 , Martin Escardo fornece um algoritmo que pode fornecer o que você está procurando:

  1. Vá para a biblioteca.
  2. Escolha um livro sobre topologia.
  3. Escolha um teorema.
  4. Aplique o dicionário.
  5. Obtenha um teorema em computação.

http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf

Veja também este artigo

NietzscheanAI
fonte
2
O dicionário é uma correspondência entre termos em topologia (como conjunto aberto) e computabilidade (como conjunto semi-decidível).
Mitch
talvez essa seja a resposta aceita #
Nikos M.
@NikosM. Eu ficaria surpreso com a primeira resposta e esta e a resposta aceita foram aceitas por um tempo, por isso prefiro não alterá-la. Se houvesse uma resposta mesclada com tudo, talvez, mas essa pergunta provavelmente se tornaria um wiki da comunidade.
Joshua Herman
@ JoshuaHerman, com certeza eu entendo, embora algumas vezes eu tenha mudado a resposta aceita à medida que meu conhecimento foi atualizado e outra resposta mais ao ponto da pergunta apareceu. De qualquer forma, sobre o tópico, você descobrirá que há muito mais analogias com outras áreas da matemática (por exemplo, não apenas entre complexidade da topologia) Por exemplo, uma área que tem esse potencial (e foi inspirada pela topologia) é teoria de categorias
Nikos M.
3

Algumas referências recentes aqui da Topologia Algébrica e da dureza UGC - Morse Theory , e outra referência Conjectura de Jogos Exclusivos e Topologia Computacional . O último é sobre cobrir espaços de gráficos e "levantamento" de gráficos, e pode apontar para um vínculo mais profundo entre Topologia e a Conjectura de Jogos Exclusivos.

user3483902
fonte