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

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ą?

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.

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 ...!