Program GCT Mulmuleya

38

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.

Anonimowy
źródło
12
Czy widziałeś samouczek Mulmuleya na FOCS (dostępny na techtalks.tv/talks/1301 ) i czy przeczytałeś ekspozycję Kena Regana: theorie.informatik.uni-ulm.de/Personen/toran/beatcs/… ? Mulmuley zdecydowanie dał intuicję, dlaczego uważa, że ​​jego program jest wykonalny (i myślę, że twierdzi, że jest nawet w pewnym stopniu konieczny), a także dlaczego jest trudny.
Sasho Nikolov
5
Powiązane posty na blogu: 1 , 2 . Również Scott pisze: „Program GCT Mulmuley jest jedynym podejściem do P vs NP Widziałem, że nawet ma poważne aspiracje do«wiedzieć»wiele technik nietrywialnych do rozwiązywania problemów w P (przynajmniej, dopasowanie i programowanie liniowe) Dla mnie jest to prawdopodobnie najsilniejszy argument na korzyść GCT. ”
Kaveh
7
Myślę, że GCT dąży do VP vs. VNP, a nie P vs. NP.
Iddo Tzameret,
6
@Iddo: W rzeczywistości może być ukierunkowany na wiele rzeczy (więcej niż jest obecnie skierowany). Dla "perm v DET na ", jest skierowana w ¯ V P w s vs V N P (patrz arxiv.org/abs/0907.2850 ). Jednak dla pól skończonych i dla funkcji innych niż perm i det, może być skierowany bezpośrednio na P vs NP. CVPws¯VNP
Joshua Grochow
4
@Mohammad: To, że rozwiązanie byłoby nieoczekiwane i wymagałoby całkowicie nowatorskich pomysłów, nie oznacza, że ​​nie tak będzie. Rzeczywiście wielu już wierzy, że rozwiązywanie P vs NP dowolną metodą będzie wymagało zupełnie nowych pomysłów ...
Joshua Grochow

Odpowiedzi:

23

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

    • 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 3n2+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.32n2+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).

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

  3. 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ę.

Joshua Grochow
źródło
1
@ user124864: Zasadniczo tak. GCT to tylko podejście do pokazywania dolnych granic, niezależnie od tych dolnych granic. Wygląda na to, że powinna działać lepiej dla funkcji charakteryzujących się ich symetriami, ale ta ostatnia właściwość nie zależy od wartości liczbowej dolnej granicy, którą chcesz pokazać (np. Quasipoly vs exp).
Joshua Grochow