Kohomologiczne podejście do złożoności logicznej

33

Kilka lat temu była praca Joela Friedmana związana z dolnymi granicami obwodu z kohomologią Grothendiecka (patrz dokumenty: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ). Czy ten sposób myślenia przyniósł jakieś nowe spojrzenie na złożoność logiczną, czy pozostaje raczej matematyczną ciekawością?

Marcin Kotowski
źródło
4
Jestem bardzo ciekawa odpowiedzi na to pytanie. Oczywiście najłatwiej byłoby wysłać wiadomość e-mail do Joela Friedmana :)
Suresh Venkat

Odpowiedzi:

28

Korespondowałem z Joelem Friedmanem około 3 lata temu na ten temat. W tym czasie powiedział, że jego podejście nie doprowadziło do żadnego nowego znaczącego wglądu w teorię złożoności, choć nadal uważał, że jest to obiecująca metoda.

Zasadniczo Friedman próbuje sformułować problemy złożoności obwodu w języku krążków w topologii Grothendiecka. Mamy nadzieję, że proces ten pozwoli zastosować intuicję geometryczną do problemu znalezienia dolnych granic obwodu. Chociaż z pewnością warto sprawdzić, czy ścieżka ta prowadzi gdziekolwiek, istnieją heurystyczne powody do sceptycyzmu. Geometryczna intuicja działa najlepiej w kontekście gładkich odmian lub rzeczy, które są wystarczająco podobne do gładkich odmian, że intuicja nie ulega całkowitemu załamaniu. Innymi słowy, potrzebujesz pewnej struktury , aby intuicja geometryczna uzyskała przyczółek. Ale dolne granice obwodu z samej swojej natury muszą konfrontować się z dowolnymi obliczeniami, które trudno dokładnie przeanalizować, ponieważ wydają się tak pozbawione struktury. Friedman przyznaje z góry, że topologie Grothendiecka, które uważa za wysoce kombinatoryczne i dalekie od zwykłych przedmiotów badań w geometrii algebraicznej.

Na marginesie, powiedziałbym, że ważne jest, aby nie ekscytować się pomysłem tylko dlatego, że używa on nieznanych maszyn o dużej mocy. Maszyneria może być bardzo skuteczna w rozwiązywaniu problemów, dla których została zaprojektowana, ale aby była przydatna do atakowania znanego trudnego problemu w innej dziedzinie, musi istnieć przekonujący argument, dlaczego zagraniczna maszyneria jest dobrze przystosowana do rozwiązania podstawowego przeszkoda w problemie zainteresowania.

Timothy Chow
źródło
4
Oczywiście wysiłki Mulmuleya przebiegają zgodnie z „podobnymi” liniami w sensie używania „gładkich struktur”, ale przygląda się problemom, które pozwalają na początek niezmiennym geometrycznym niezmiennikom.
Suresh Venkat,
2
@Suresh: Masz rację, że podejście Mulmuley-Sohoni jest inne, ale podstawowy problem radzenia sobie z arbitralnym obliczeniem wciąż czai się w tle, więc sprawiedliwe jest pytanie, jak można się z nim uporać. W tej chwili wydaje mi się, że nikt tak naprawdę nie wie, dlatego ludzie z GCT nie obiecują spektakularnych przełomów w najbliższym czasie.
Timothy Chow,
w rzeczy samej. ciekawie jest zobaczyć artykuł STOC 2011, który używa GCT do granic mnożenia macierzy (a Ketan wspominał o tym wyniku w swoim tutorialu na FOCS)
Suresh Venkat
1
@Suresh: Jeśli mówisz o artykule Buergisser / Ikenmeyer, myślę, że mówi on znacznie więcej o limitach podejścia GCT niż o tym, jak udowodnić dolne granice.
5501
1
@Neel, nie mam odpowiedzi, ale zastanawiam się, czy to zasługuje na własne pytanie.
Suresh Venkat,
16

Myślę, że Timothy Chow ma dokładnie rację. Mam własną listę pomysłów na pranie obejmującą odmiany „gładkie” lub koncepcje, takie jak zliczanie połączonych elementów lub monomianów, które pasują do kilku najniższych szczebli „drabiny kohomologicznej” - wszystkie z nich nie są przewidywane przez ( wariacje na temat) konstrukcja Mayr-Meyer pokazująca kompletność EXPSPACE różnych problemów związanych z GCT. Mój jedyny riff w ostatnim akapicie jest taki, że myślę, że potrzebna jest jakaś maszyna o dużej mocy ...!

Kenneth W. Regan
źródło