Aufsätze zum Zusammenhang zwischen rechnerischer Komplexität und algebraischer Geometrie / Topologie?

22

Ich fragte mich, welche Papiere ich lesen sollte, um diese Frage zu verstehen

Eine unerwartete Verbindung zu anderen Bereichen der Mathematik wie der algebraischen Geometrie oder der höheren Kohomologie. Vielleicht ist sogar ein Bereich der Mathematik noch nicht erschlossen. Vielleicht wird jemand eine ganz neue Richtung für die Mathematik entwickeln, um die Frage von P gegen NP zu lösen. -Für Fortnow 2002

Eine andere Formulierung der Frage wäre: "Welche Artikel sollte ich lesen, um eine Verbindung von der Komplexität der Berechnungen zur algebraischen Geometrie / Topologie herzustellen?"

Ich habe mich bereits mit der Theorie der geometrischen Komplexität befasst . Auch Artikel in Topological Quantum Computation, in denen ich genügend Artikel gelesen habe, die ich bereits kenne. Vermisse ich etwas?

cc.complexity-theory reference-request gct algebraic-topology Joshua Herman
quelle
1
Darf ich eine Änderung des Titels vorschlagen? So etwas wie "Artikel über die Beziehung zwischen rechnerischer Komplexität und algebraischer Geometrie / Topologie".
Kaveh
Könnten Sie Ihre Frage etwas näher erläutern? Ich würde denken, dass jeder etwas von dieser Zeile vermissen würde, wenn diese Zeile wahr ist, da er über "Unbekannte" spricht. Ich denke, Professor Sureshs Antwort auf die unteren Grenzen ist eine gute Referenz.
vs
2
Vielleicht möchten Sie auch diese verwandte Frage untersuchen: cstheory.stackexchange.com/questions/2898/…
Martin Schwarz
1
Ich fand auch dieses Papier cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf
Joshua Herman

Antworten:

10
vs
quelle
Ist dies ein explizites Beispiel für die etale Kohomologie? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf
Joshua Herman
Bitte beziehen Sie sich hier. www-math.mit.edu/~kedlaya/18.787/intro.pdf
vs
1
Die Arbeit von Sudan und Guruswami befasst sich hauptsächlich mit der Listendekodierung (die auch die AG-Codes betrifft) - ein Thema, das Ende der 90er Jahre aufkam und in den 2000er Jahren stark weiterentwickelt wurde. Die algebraische Geometriemethode erschien in Arbeiten von Goppa in den 80er Jahren und wurde von Tsfasman und Vladutc und vielen anderen in den 90er Jahren entwickelt. Persönlich würde ich das Papier vorschlagen: Hoholdt, van Lint, Pellikaan, Algebraische Geometrie-Codes, 1998.
Artem Pelenitsyn
1
Bezüglich der computational AG würde ich Bücher von Cox-Little-O'Shea und Schenck vorschlagen, aber dieses Thema ist ein wenig irrelevant für die von Joshua angeforderte „Verbindung von rechnerischer Komplexität zu algebraischer Geometrie“.
Artem Pelenitsyn
4

In Folie 26 stellt Martin Escardo einen Algorithmus zur Verfügung, mit dem Sie möglicherweise das finden, wonach Sie suchen:

  1. Geh in die Bibliothek.
  2. Wählen Sie ein Buch zur Topologie.
  3. Wählen Sie einen Satz.
  4. Wenden Sie das Wörterbuch an.
  5. Holen Sie sich einen Satz in die Berechnung.

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

Siehe auch dieses Papier

NietzscheanAI
quelle
2
Das Wörterbuch ist eine Entsprechung zwischen Begriffen in der Topologie (wie eine offene Menge) und der Berechenbarkeit (wie eine halbentscheidbare Menge).
Mitch,
Vielleicht sollte dies die akzeptierte Antwort sein
Nikos M.
@NikosM. Ich würde mit der ersten Antwort zerrissen sein und diese und die akzeptierte Antwort wurden für eine Weile akzeptiert, also ändere ich sie lieber nicht. Wenn es eine zusammengeführte Antwort mit allem geben würde, aber dann würde diese Frage wahrscheinlich zu einem Community-Wiki.
Joshua Herman
@JoshuaHerman, sicher, ich verstehe, obwohl ich manchmal die akzeptierte Antwort geändert habe, als mein Wissen aktualisiert wurde und eine andere Antwort mehr zum Punkt der Frage erschien. Wie auch immer, in Bezug auf das Thema werden Sie feststellen, dass es noch viel mehr Analogien zu anderen Bereichen der Mathematik gibt (dh nicht nur zwischen Topologie-Komplexität). Zum Beispiel zu einem Bereich, der dieses Potenzial hat (und von der Topologie inspiriert wurde). ist Kategorietheorie
Nikos M.
3

Einige neuere Referenzen hier aus der algebraischen Topologie und der UGC-Härte- Morse-Theorie sowie eine weitere Referenz Unique Games Conjecture und Computational Topology . Bei letzterem geht es darum, Bereiche von Graphen abzudecken und Graphen zu "heben" und auf eine tiefere Verbindung zwischen der Topologie und der Unique Games Conjecture hinzuweisen.

user3483902
quelle