Articles sur la relation entre la complexité de calcul et la géométrie / topologie algébrique?

22

Je me demandais quels papiers je devrais lire pour comprendre cette question

Une connexion inattendue à d'autres domaines des mathématiques tels que la géométrie algébrique ou la cohomologie supérieure. Peut-être même un domaine des mathématiques pas encore développé. Peut-être que quelqu'un développera une toute nouvelle direction pour les mathématiques afin de traiter la question P contre NP. -De Fortnow 2002

Une autre formulation de la question serait "Quels articles dois-je lire pour créer un lien entre la complexité de calcul et la géométrie / topologie algébrique?"

J'ai déjà examiné la théorie de la complexité géométrique . Également des articles sur le calcul quantique topologique dont j'ai lu suffisamment d'articles que je connais déjà bien. Suis-je en train de manquer quelque chose?

cc.complexity-theory reference-request gct algebraic-topology Joshua Herman
la source
1
Puis-je suggérer une modification du titre? Quelque chose comme "Articles sur la relation entre la complexité de calcul et la géométrie / topologie algébrique".
Kaveh
Pourriez-vous élaborer un peu votre question? Je pense que tout le monde manquerait quelque chose de cette ligne si cette ligne est vraie puisqu'il parle des "inconnus". Je pense que la réponse du professeur Suresh ci-dessous sur les limites inférieures est une bonne référence.
vs
2
Vous pouvez également examiner cette question connexe: cstheory.stackexchange.com/questions/2898/…
Martin Schwarz
1
J'ai également trouvé cet article cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf
Joshua Herman

Réponses:

10
contre
la source
Est-ce un exemple explicite de cohomologie étale? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf
Joshua Herman
Veuillez vous référer ici. www-math.mit.edu/~kedlaya/18.787/intro.pdf
vs
1
Les travaux du Soudan et de Guruswami sont principalement consacrés au décodage de listes (qui concerne également les codes AG) - sujet qui a été soulevé à la fin des années 90 et qui a été fortement développé à partir des années 2000. La méthode de la géométrie algébrique est apparue à 80 s dans des articles de Goppa et a été développée par Tsfasman et Vladutc et bien d'autres à 90 s. Personnellement, je suggère le document: Hoholdt, van Lint, Pellikaan, Codes de géométrie algébrique, 1998.
Artem Pelenitsyn
1
En ce qui concerne le calcul AG, je suggérerais des livres de Cox — Little — O'Shea et Schenck, mais ce sujet est un peu hors de propos à la “connexion de la complexité du calcul à la géométrie algébrique” qui a été demandée par Joshua.
Artem Pelenitsyn
4

Dans la diapositive 26 , Martin Escardo fournit un algorithme qui pourrait vous donner ce que vous recherchez:

  1. Allez à la bibliothèque.
  2. Choisissez un livre sur la topologie.
  3. Choisissez un théorème.
  4. Appliquez le dictionnaire.
  5. Obtenez un théorème de calcul.

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

Voir aussi cet article

NietzscheanAI
la source
2
Le dictionnaire étant une correspondance entre des termes de topologie (comme ensemble ouvert) et de calculabilité (comme ensemble semi-décidable).
Mitch
peut-être que cela devrait être la réponse acceptée
Nikos M.
@NikosM. Je serais déchiré par la première réponse et celle-ci et la réponse acceptée ont été acceptées pendant un certain temps, donc je préfère ne pas la changer. S'il y avait une réponse fusionnée avec tout, peut-être, mais alors cette question deviendrait probablement un wiki communautaire.
Joshua Herman
@JoshuaHerman, bien sûr que je comprends, bien que moi-même j'ai parfois changé la réponse acceptée au fur et à mesure que mes connaissances étaient mises à jour et une autre réponse plus pertinente à la question est apparue. Quoi qu'il en soit, sur le sujet, vous découvrirez qu'il y a beaucoup plus d'analogies avec d'autres domaines des mathématiques (i, e non seulement entre la topologie et la complexité) Par exemple, un domaine qui a ce potentiel (et qui a été inspiré par la topologie) est la théorie des catégories
Nikos M.
3

Quelques références récentes ici tirées de la topologie algébrique et de la dureté UGC - théorie de Morse , et une autre référence à la conjecture de jeux uniques et à la topologie computationnelle . Cette dernière concerne la couverture d'espaces de graphes et la "levée" de graphes, et pourrait indiquer un lien plus profond entre la topologie et la conjecture des jeux uniques.

user3483902
la source