Program GCT Mulmuleya

Czasami twierdzi się, że teoria złożoności geometrycznej Ketana Mulmuleya jest jedynym wiarygodnym programem do rozstrzygania otwartych pytań teorii złożoności, takich jak pytanie P vs. NP. Było wiele pozytywnych komentarzy od słynnych teoretyków złożoności na temat programu. Według Mulmuleya osiągnięcie pożądanych rezultatów zajmie dużo czasu. Wejście w ten obszar nie jest łatwe dla teoretyków ogólnej złożoności i wymaga znacznych wysiłków, aby opanować geometrię algebraiczną i teorię reprezentacji.

1. Dlaczego GCT jest uważany za zdolny do rozliczenia P vs. NP? Jaka jest wartość roszczenia, jeśli oczekuje się, że dotarcie tam zajmie ponad 100 lat? Jakie są jego zalety w stosunku do innych obecnych podejść i tych, które mogą wzrosnąć w ciągu najbliższych 100 lat?

2. Jaki jest obecny stan programu?

3. Jaki jest następny cel programu?

4. Czy była jakaś podstawowa krytyka programu?

Wolałbym odpowiedzi, które są zrozumiałe dla ogólnej teoretyki złożoności, przy założeniu minimalnego tła z geometrii algebraicznej i teorii reprezentacji.

Jak zauważyło wielu innych, wiele z tych pytań zostało już powiedzianych przez Mulmuleya, Regana i innych. Przedstawię tutaj krótkie podsumowanie tego, co według mnie jest kluczowymi kwestiami, o których jeszcze nie wspomniano w komentarzach.

1. Co do tego, dlaczego uważa się, że GCT jest w stanie wykazać wiele odpowiedzi zostało już podanych gdzie indziej i w powyższych komentarzach, choć myślę, że nikt jeszcze nie wspomniał, że wydaje się unikać znanych barier (relatywizacja, algebriacja, dowody naturalne) ). Jeśli chodzi o jego wartość - myślę, że nawet jeśli zajmie nam to 100 lat, po drodze dowiemy się czegoś nowego o złożoności, badając ją pod tym kątem.$P \neq NP$

2. • Poczyniono pewne postępy w zrozumieniu odmian algebraicznych, reprezentacji i pytań algorytmicznych pojawiających się w GCT. Głównymi znanymi mi badaczami, którzy wykonali nad tym prace (w określonej kolejności): P. Burgisser, C. Ikenmeyer, M. Christandl, JM Landsberg, KV Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar i oczywiście K. Mulmuley i M. Sohoni.

   • Mówiąc konkretniej, Burgisser i Ikenmeyer właśnie przedstawili (STOC 2011) pewne skromne dolne granice mnożenia macierzy przy użyciu metody GCT ( , w porównaniu do obecnie najbardziej znanych $n^2 + 2$). Chociaż te dolne granice nie są nowymi granicami, dają one co najmniej pewien dowód słuszności koncepcji, w tym sensie, że obiekty teoretyczne reprezentujące hipotezę istnienia w GCT istnieją dla tych skromnych dolnych granic tego problemu modelu.$\frac{3}{2}n^2 +O(n)$

   • N. Kayal ma kilka artykułów na temat algorytmicznego pytania o testowanie, gdy jeden wielomian znajduje się na orbicie drugiego lub jest rzutem innego. Pokazuje, że na ogół problemy te są trudne dla NP, ale w przypadku funkcji specjalnych, takich jak stałe, wyznaczniki i elementarne wielomiany symetryczne, problemy te są rozstrzygalne w P. zamknięcie - są w P dla funkcji specjalnych, takich jak wyznacznik).

3. Nie mam nic bardziej szczegółowego do powiedzenia na ten temat niż odpowiedź na pytanie 2.

4. O ile mi wiadomo, nie doszło do fundamentalnej krytyki w tym sensie, że nie spotkałem się z żadną krytyką, która w jakikolwiek sposób zdyskredytuje program. Z pewnością dyskutowano o tym, dlaczego takie techniki powinny być potrzebne, o wartości programu, biorąc pod uwagę oczekiwane horyzonty czasowe itp., Ale scharakteryzowałbym je bardziej jako zdrową dyskusję niż podstawową krytykę.

Myślę, że ten artykuł Ketana D. Mulmuleya odpowie na co najmniej pytanie nr 1 (być może 2) na temat P vs. NP i teorii złożoności geometrycznej