¿Artículos sobre la relación entre la complejidad computacional y la geometría / topología algebraica?

22

Me preguntaba qué documentos debería leer para entender esta pregunta

Una conexión inesperada con otras áreas de las matemáticas, como la geometría algebraica o la cohomología superior. Quizás incluso un área de matemáticas aún no desarrollada. Quizás alguien desarrolle una dirección completamente nueva para las matemáticas con el fin de manejar la pregunta P versus NP. -Desde Fortnow 2002

Otra formulación de la pregunta sería "¿Qué documentos debo leer para crear una conexión entre la complejidad computacional y la geometría / topología algebraica?"

Ya he visto la teoría de la complejidad geométrica . También documentos en Computación cuántica topológica que he leído suficientes documentos que ya estoy familiarizado con el campo. ¿Me estoy perdiendo algo?

cc.complexity-theory reference-request gct algebraic-topology Joshua Herman
fuente
1
¿Puedo sugerir un cambio en el título? Algo así como "Documentos sobre la relación entre la complejidad computacional y la geometría / topología algebraica".
Kaveh
¿Podrías elaborar tu pregunta un poco? Creo que todos extrañarían algo de esa línea si esa línea es cierta ya que está hablando de "incógnitas". Creo que la respuesta del profesor Suresh a continuación en los límites inferiores es una buena referencia.
vs
2
También puede consultar esta pregunta relacionada: cstheory.stackexchange.com/questions/2898/…
Martin Schwarz
1
También encontré este documento cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf
Joshua Herman

Respuestas:

10
vs
fuente
¿Es este un ejemplo explícito de etale cohomology? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf
Joshua Herman el
Por favor refiérase aquí. www-math.mit.edu/~kedlaya/18.787/intro.pdf
vs
1
El trabajo de Sudán y Guruswami se dedica principalmente a la decodificación de listas (que, bueno, también se refiere a los códigos AG), tema que surgió a fines de los 90 y se desarrolló en gran medida a los 2000. El método de geometría algebraica apareció a los 80 s en los documentos de Goppa, y fue desarrollado por Tsfasman y Vladutc y muchos otros a los 90 s. Personalmente, sugeriría el artículo: Hoholdt, van Lint, Pellikaan, códigos de geometría algebraica, 1998.
Artem Pelenitsyn
1
En cuanto al AG computacional, sugeriría libros de Cox-Little-O'Shea y Schenck, pero este tema es un poco irrelevante para la "conexión de la complejidad computacional a la geometría algebraica" que Joshua solicitó.
Artem Pelenitsyn
4

En la Diapositiva 26 , Martin Escardo proporciona un algoritmo que podría darle lo que está buscando:

  1. Ve a la biblioteca.
  2. Elija un libro sobre topología.
  3. Elige un teorema.
  4. Aplica el diccionario.
  5. Obtenga un teorema en computación.

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

Ver también este documento

NietzscheanAI
fuente
2
El diccionario es una correspondencia entre términos en topología (como conjunto abierto) y computabilidad (como conjunto semidecidible).
Mitch
tal vez esta debería ser la respuesta aceptada
Nikos M.
@NikosM. Sería desgarrado con la primera respuesta y esta y la respuesta aceptada ha sido aceptada por un tiempo, así que prefiero no cambiarla. Si hubiera una respuesta combinada con todo tal vez, pero esta pregunta probablemente se convertiría en un wiki de la comunidad.
Joshua Herman
@JoshuaHerman, seguro que entiendo, aunque a veces yo mismo he cambiado la respuesta aceptada a medida que mi conocimiento se actualizaba y aparecía otra respuesta más al punto de la pregunta. De todos modos, sobre el tema, descubrirá que también hay muchas más analogías con otras áreas de las matemáticas (es decir, no solo entre topología-complejidad). Por ejemplo, un área que tiene este potencial (y se inspiró en la topología) es teoría de la categoría
Nikos M.
3

Algunas referencias recientes aquí de Topología algebraica, y dureza UGC - Morse Theory , y otra referencia Conjetura de juegos únicos y Topología computacional . El último se trata de cubrir espacios de gráficos y "levantar" los gráficos, y podría señalar un vínculo más profundo entre la topología y la conjetura de juegos únicos.

usuario3483902
fuente