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?

— 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

13

W tle zdecydowanie powinieneś przestudiować pracę Ben-Or na dolnych granicach , a także papier P vs NC Mulmuleya .

— Suresh Venkat
źródło

10

Mnożenie macierzy (tam zawarte odniesienia)
Kryptografia oparta na parowaniu

Koncentruje się na tym, co można zrobić z niektórymi hipotetycznymi parami wieloliniowymi. Przypuszcza się, że nie istnieją one w geometrii algebraicznej. Jeśli okaże się inaczej, być może możesz wygłosić wykład podczas następnego ICM
„Wyraźna” kohomologia etale i obliczenia w geometrii arytmetycznej (książka faktycznie działa z jawną kohomologią etale)
Obliczeniowo rozwiązujące osobliwości odmian algebraicznych.
Książka Tsfasmana-Manina i praca dekodująca Sudan-Guruswami List na temat algebraiczno-geometrycznych aspektów teorii kodowania.

— 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:

Idź do biblioteki.
Wybierz książkę o topologii.
Wybierz twierdzenie.
Zastosuj słownik.
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