Artykuły na temat związku między złożonością obliczeniową a geometrią / topologią algebraiczną?

22

Zastanawiałem się, jakie artykuły powinienem przeczytać, aby zrozumieć to pytanie

Nieoczekiwane połączenie z innymi dziedzinami matematyki, takimi jak geometria algebraiczna lub wyższa kohomologia. Być może nawet dziedzina matematyki nie została jeszcze rozwinięta. Być może ktoś opracuje zupełnie nowy kierunek matematyki, aby poradzić sobie z pytaniem P kontra NP. -Od Fortnow 2002

Innym sformułowaniem pytania byłoby „Jakie artykuły powinienem przeczytać, aby stworzyć połączenie od złożoności obliczeniowej do geometrii / topologii algebraicznej?”

Mam spojrzał na Geometryczna teoria złożoności już. Także artykuły z topologicznego obliczenia kwantowego, które przeczytałem wystarczająco dużo artykułów, które już znam. Czy coś mi brakuje?

cc.complexity-theory reference-request gct algebraic-topology Joshua Herman
źródło
1
Czy mogę zasugerować zmianę tytułu? Coś w rodzaju „Dokumenty na temat związku między złożonością obliczeniową a geometrią / topologią algebraiczną”.
Kaveh
Czy mógłbyś trochę rozwinąć swoje pytanie? Sądzę, że wszyscy przegapiliby coś z tej linii, jeśli ta linia jest prawdziwa, ponieważ mówi o „niewiadomych”. Myślę, że odpowiedź profesora Suresha na niższych granicach jest dobrym odniesieniem.
porównaniu z
2
Możesz także przyjrzeć się temu pokrewnemu pytaniu: cstheory.stackexchange.com/questions/2898/…
Martin Schwarz
1
Znalazłem również ten artykuł cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf
Joshua Herman

Odpowiedzi:

10
vs
źródło
Czy to wyraźny przykład kohomologii etale? math.mcgill.ca/goren/SeminarOnCohomology/etale2.pdf
Joshua Herman
Proszę odnieść się tutaj. www-math.mit.edu/~kedlaya/18.787/intro.pdf
porównaniu z
1
Praca Sudanu i Guruswami poświęcona jest głównie dekodowaniu list (które, no cóż, dotyczy również kodów AG) - tematu, który podniósł się pod koniec lat 90-tych i został mocno rozwinięty w 2000 roku. Metoda geometrii algebraicznej pojawiła się w latach 80-tych w pracach Goppy, a została opracowana przez Tsfasmana i Vladutca oraz wielu innych w latach 90-tych. Osobiście sugerowałbym artykuł: Hoholdt, van Lint, Pellikaan, Algebraiczne kody geometrii, 1998.
Artem Pelenitsyn
1
Jeśli chodzi o AG obliczeniową, sugerowałbym książki Coxa-Little-O'Shei i Schencka, ale ten temat jest nieco nieistotny dla „związku złożoności obliczeniowej z geometrią algebraiczną”, o który poprosił Joshua.
Artem Pelenitsyn,
4

W slajdzie 26 Martin Escardo przedstawia algorytm, który może dać ci to, czego szukasz:

  1. Idź do biblioteki.
  2. Wybierz książkę o topologii.
  3. Wybierz twierdzenie.
  4. Zastosuj słownik.
  5. Uzyskaj twierdzenie w obliczeniach.

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

Zobacz także ten artykuł

NietzscheanAI
źródło
2
Słownik będący korespondencją między terminami w topologii (jak zbiór otwarty) i obliczalności (jak zbiór częściowo rozstrzygalny).
Mitch
może to powinna być zaakceptowana odpowiedź
Nikos M.,
@NikosM. Byłbym rozdarty pierwszą odpowiedzią, a ta i zaakceptowana odpowiedź została na jakiś czas przyjęta, więc raczej jej nie zmieniam. Gdyby istniała połączona odpowiedź na wszystko, być może, ale to pytanie prawdopodobnie stałoby się wiki społeczności.
Joshua Herman,
@JoshuaHerman, na pewno rozumiem, chociaż ja czasami zmieniłem zaakceptowaną odpowiedź, ponieważ moja wiedza została zaktualizowana i pojawiła się kolejna odpowiedź bardziej na temat pytania. W każdym razie na ten temat dowiesz się, że istnieje wiele innych analogii z innymi dziedzinami matematyki (tj. Nie tylko między złożonością topologii) Na przykład obszar, który ma ten potencjał (i został zainspirowany topologią) jest teoria kategorii
Nikos M.
3

Niektóre najnowsze odniesienia tutaj z Topologii Algebraicznej i twardości UGC - Teoria Morse'a , a także inne odniesienia Unique Games Conjecture and Computational Topology . Ten ostatni dotyczy pokrywania przestrzeni wykresów i „podnoszenia” wykresów i może wskazywać na głębsze powiązanie między topologią a hipotezą unikalnych gier.

użytkownik3483902
źródło