Wyjaśnienie w stylu Wikipedii teorii złożoności geometrycznej

Czy ktoś może przedstawić zwięzłe wyjaśnienie podejścia GCT Mulmuleya, zrozumiałe dla osób nie będących ekspertami? Wyjaśnienie, które byłoby odpowiednie dla strony Wikipedii na ten temat (która jest w tej chwili krótka).

Motywacja: „Czytam” książkę Scotta Aaronsona Quantum Computing od czasów Demokryta z moim przyjacielem, który jest badaczem teorii strun. W przedmowie książki Aaronson nazywa GCT „teorią strun informatyki”. Jako teoretyk strun mój przyjaciel podekscytował się tym twierdzeniem i zapytał mnie, czym jest GCT. W tym momencie ze wstydem zdałem sobie sprawę, że nie mam gotowej na Wikipedię odpowiedzi na jego pytanie.

Nie jestem do końca pewien, jaki poziom jest odpowiedni dla artykułu w Wikipedii (wydaje się, że różne artykuły dotyczą różnych poziomów wiedzy) lub dokładnie tego, czego szukasz. Oto próba, ale jestem otwarty na opinie.

Teoria złożoności geometrycznej proponuje zbadanie złożoności obliczeniowej funkcji obliczeniowych (powiedzmy wielomianów) poprzez wykorzystanie nieodłącznych symetrii złożoności i wszelkich dodatkowych symetrii badanych funkcji.

Podobnie jak w przypadku wielu poprzednich podejść, ostatecznym celem jest oddzielenie dwóch klas złożoności , pokazując, że istnieje wielomian który przyjmuje funkcje jako dane wejściowe (powiedzmy , przez ich wektory współczynników) takie, że znika na każdej funkcji ale nie znika na niektórych funkcjach .$\mathcal{C}_{easy}, \mathcal{C}_{hard}$$p$$f$$p$$f \in \mathcal{C}_{easy}$$g_{hard} \in \mathcal{C}_{hard}$

Pierwszą kluczową ideą (por. [GCT1, GCT2]) jest użycie symetrii do uporządkowania nie samych funkcji, ale do uporządkowania ( algebro-geometrycznych ) właściwości tych funkcji, zarejestrowanych przez wielomiany, takie jak powyżej. Umożliwia to wykorzystanie teorii reprezentacji do próby znalezienia takiego . Podobne idee związane z teorią reprezentacji i geometrią algebraiczną były wcześniej stosowane w geometrii algebraicznej, ale o ile mi wiadomo, nigdy nie w ten sposób.$p$$p$

Drugim kluczowym pomysłem (por. [GCT6]) jest znalezienie algorytmów kombinatorycznych (i czasu wielomianowego) dla powstałych problemów teoretycznych reprezentacji, a następnie inżynieria wsteczna tych algorytmów, aby pokazać, że takie istnieje. Można to przyjąć w duchu użycia programowania liniowego (algorytmu) do udowodnienia pewnych twierdzeń czysto kombinatorycznych.$p$

Rzeczywiście, [GCT6] sugeruje redukcję problemów teoretycznych przedstawionych powyżej do problemów z programowaniem liczb całkowitych , a następnie wykazanie, że wynikowe adresy IP są rozwiązywane przez ich relaksacje LP, i wreszcie podanie algorytmów kombinatorycznych dla powstałych LP. Domysły w [GCT6] same w sobie są motywowane znanymi wynikami inżynierii odwrotnej dla współczynników Littlewooda-Richardsona, analogicznym, ale łatwiejszym problemem w teorii reprezentacji. W przypadku współczynników LR na pierwszym miejscu była reguła kombinatoryczna Littlewooda-Richardsona . Później Berenstein i Zelevinsky [BZ] oraz Knutson i Tao [KT] (patrz [KT2] dla przyjaznego przeglądu) podali IP dla współczynników LR. Knutson i Tao udowodnili również hipotezę nasycenia, co sugeruje, że IP rozwiązuje się poprzez relaksację LP (por. [GCT3, BI]).

Wyniki [GCT5] pokazują, że jawne derandomizowanie lematu normalizacyjnego Noether jest zasadniczo równoważne z notorycznie otwartym problemem w teorii złożoności derandomizacji czarnej skrzynki w testach tożsamości wielomianowej . Z grubsza to pasuje do większego programu, że znalezienie wyraźnej podstawy dla funkcji które (nie) znikają na (w tym przypadku klasa, dla której wyznacznik jest kompletny) może być używane do wyprowadzenia reguły kombinatorycznej dla pożądanego problemu w teorii reprezentacji, tak jak miało to miejsce w innych ustawieniach geometrii algebraicznej. Etap pośredni tutaj byłoby znaleźć podstawę dla tych , że (nie) znikają na normalizację$p$$\mathcal{C}_{easy}$$p$$\mathcal{C}_{easy}$ , który dzięki lepszej odmianie algebraicznej - innymi słowy, ma na celu derandomizację normalizacji Noether dla DET.

Przykłady symetrii złożoności i funkcji

Na przykład złożoność funkcji - w przypadku większości naturalnych pojęć złożoności - pozostaje niezmieniona, jeśli permutujemy zmienne przez jakąś permutację . Zatem permutacje są same w sobie symetriami złożoności. W przypadku niektórych pojęć złożoności (np. W złożoności obwodu algebraicznego) wszystkie odwracalne liniowe zmiany zmiennych są symetriami.$f(x_1, \dotsc, x_n)$$f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$$\pi$

Poszczególne funkcje mogą mieć dodatkowe symetrie. Na przykład wyznacznik ma symetrie dla wszystkich macierzy tak że . (Z tego, co niewiele z tego nauczyłem, rozumiem, że jest to analogiczne do zjawiska spontanicznego łamania symetrii w fizyce.)$\det(X)$$\det(AXB) = \det(X^{T}) = \det(X)$$A,B$$\det(AB) = 1$

Trochę ostatnich postępów [ta sekcja zdecydowanie niekompletna i bardziej techniczna, ale pełne konto zajmie dziesiątki stron ... Chciałem tylko podkreślić niektóre ostatnie postępy]

Burgisser i Ikenmeyer [BI2] wykazali dolną granicę przy mnożeniu macierzy po programie GCT, o ile stosowali reprezentacje z wielokrotnością zerową i niezerową. Landsberg i Ottaviani [LO] podali najlepiej znaną dolną granicę zasadniczo na granicy stopnia mnożenia macierzy, stosując teorię reprezentacji do organizowania właściwości algebraicznych, ale nie stosując mnogości reprezentacji ani reguł kombinatorycznych.$\frac{3}{2}n^2$$2n^2$

Kolejnym problemem po współczynnikach Littlewooda-Richardsona są współczynniki Kroneckera . Pojawiają się one zarówno w serii problemów, które, jak się podejrzewa, ostatecznie osiągają teoretyczne problemy reprezentacyjne pojawiające się w GCT, jak i bardziej bezpośrednio, jako granice mnogości w podejściu GCT do mnożenia macierzy i trwałej kontra wyznacznik. Znalezienie reguły kombinatorycznej dla współczynników Kroneckera jest od dawna otwartym problemem w teorii reprezentacji; Blasiak [B] niedawno podał taką kombinatoryjną regułę dla współczynników Kroneckera z jednym kształtem haka.

Kumar [K] wykazał, że pewne reprezentacje pojawiają się w pierścieniu współrzędnych wyznacznika o niezerowej krotności, zakładając kolumnową hipotezę łacińską (por. Huang-Rota i Alon-Tarsi; przypuszczenie to również, być może nieprzypadkowo, pojawia się w [BI2 ]). Stąd te reprezentacje nie mogą być użyte do oddzielenia trwałego od wyznacznika na podstawie wielokrotności zero od niezerowych, chociaż nadal może być możliwe użycie ich do oddzielenia trwałego od wyznacznika przez bardziej ogólną nierówność między mnożnikami.

Referencje [B] J. Blasiak. Współczynniki Kroneckera dla jednego kształtu haka. arXiv: 1209.2018, 2012.

[BI] P. Burgisser i C. Ikenmeyer. Algorytm maksymalnego przepływu dla dodatnich współczynników Littlewooda-Richardsona. FPSAC 2009.

[BI2] P. Burgisser i C. Ikenmeyer. Wyraźne dolne granice za pomocą teorii złożoności geometrycznej. arXiv: 1210.8368, 2012.

[BZ] AD Berenstein i AV Zelevinsky. Potrójne krotności dla i spektrum zewnętrznej algebry reprezentacji przyległej. $\mathfrak{sl}(r+1)$J. Algebraic Combin. 1 (1992), no. 1, 7–22.

[GCT1] KD Mulmuley i M. Sohoni. Teoria złożoności geometrycznej I: Podejście do P vs. NP i powiązanych problemów. SIAM J. Comput. 31 (2), 496–526, 2001.

[GCT2] KD Mulmuley i M. Sohoni. Teoria złożoności geometrycznej II: W kierunku wyraźnych przeszkód utrudniających osadzanie się odmian odmian. SIAM J. Comput., 38 (3), 1175–1206, 2008.

[GCT3] KD Mulmuley, H. Narayanan i M. Sohoni. Teoria złożoności geometrycznej III: przy podejmowaniu decyzji o nieoszlifowaniu współczynnika Littlewooda-Richardsona. J. Algebraic Combin. 36 (2012), no. 1, 103–110.

[GCT5] KD Mulmuley. Teoria złożoności geometrycznej V: Równoważność między derandomizacją blackboksa testu tożsamości wielomianowej a derandomizacją lematu normalizacyjnego Noether. FOCS 2012, także arXiv: 1209.5993.

[GCT6] KD Mulmuley. Teoria złożoności geometrycznej VI: odwrócenie poprzez dodatni. , Raport techniczny, Wydział Informatyki, Uniwersytet Chicago, styczeń 2011.

[K] S. Kumar. Badanie reprezentacji wspieranych przez zamknięcie wyznacznika na orbicie. arXiv: 1109.5996, 2011.

[LO] JM Landsberg i G. Ottaviani. Nowe dolne granice rangi granicznej mnożenia macierzy. arXiv: 1112.6007, 2011.

[KT] A. Knutson i T. Tao. Model plastra miodu produktów . I. Dowód hipotezy nasycenia. $\text{GL}_n(\mathbb{C})$J. Amer. Matematyka Soc. 12 (1999), no. 4, 1055–1090.

[KT2] A. Knutson i T. Tao. Plaster miodu i sumy matryc hermitowskich. Uwagi Amer. Matematyka Soc. 48 (2001), no. 2, 175–186.

Niedawno udzieliłem odpowiedzi na powiązane pytanie dotyczące Mathoverflow https://mathoverflow.net/questions/277408/what-are-the-current-breakthroughs-of-geometric-complexity-theory

Ponieważ ta strona jest być może lepszym miejscem, pozwól mi po prostu powtórzyć tę odpowiedź poniżej. Odniesienia do Józefa lub Tymoteusza dotyczą innych postów dotyczących tego pytania MO.

---

Niech będzie ogólną macierzą , a stopień jednorodny wielomian podany przez wyznacznik. Niech który przyjmuje stały podmacierz i mnoży się przez ulubioną formę liniową, aby utworzyć kolejny jednorodny wielomian stopnia (można również użyć wpisu zamiast ). Ta modyfikacja nosi nazwę padding . Następnie określ liczbę $X=(X_{ij})_{1\le i,j\le n}$$n\times n$$F_1(X)={\rm det}(X)$$n$

$$F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right]$$ $m\times m$$n$$X_{11}$$X_{nn}$ $$c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \}$$ gdzie to działający na afiniczną przestrzeń wymiaru gdzie żyje, a są zamknięciami Zariski na orbitach. Wielką hipotezą w tym obszarze lub hipotezą Valianta (złożona wersja ) jest to, że rośnie szybciej niż jakikolwiek wielomian .$G$$GL(n^2)$$n^2$$X$$\overline{G\cdot F_i}$${\rm P}\neq{\rm NP}$$c(m)$$m$

Teraz, jeśli , wtedy mamy zaskakującą równoważną mapę pomiędzy stopniami części pierścieni współrzędnych tych zamknięć orbit. Gra ma więc na celu wykazanie, że tak się nie dzieje, ponieważ niewystarczająco duży w stosunku do , poprzez udowodnienie istnienia niedrożności wielokrotności , tj. Nieredukowalnej reprezentacji dla której wielokrotności spełniają $\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$$G$

$$\mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d$$ $d$$n$$m$$\lambda$ $${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)$$ lub na poziomie ideałów $${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ .$$

Optymistyczne podejście polega na próbie wykazania, że ​​istnieją przeszkody w wystąpieniu , tj. jest taka, że i . Ta nadzieja została zgnieciona w pracach Bürgissera, Ikenmeyera i Panova, o których wspomniał Timothy. Jednak możliwość wystąpienia przeszkód związanych z wielokrotnością jest nadal otwarta.$\lambda$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$

Myślę, że podejście Mulmuleya polega na próbie udowodnienia istnienia takich przeszkód związanych z licznością poprzez wykorzystanie wszystkich narzędzi dostępnych w teorii reprezentacji do obliczenia tych mnogości. Osobiście nigdy nie byłem fanem tego podejścia. Po dogłębnym przestudiowaniu teorii niezmienników XIX wieku wydaje mi się bardziej naturalne podejście do problemu separacji orbit przy użyciu wyraźnych narzędzi z tamtej epoki. Ten artykuł Gorchowa wydaje się również wskazywać w podobnym kierunku (podejrzewam, że trzeci artykuł wspomniany przez Józefa jest w tym samym duchu). W języku klasycznym (patrz Turnbull lub Littlewood ) należy jawnie skonstruować mieszany towarzyszący, który znika na$F_1$ale nie na . Tę czynność należy również wykonywać nieskończenie często ( ), aby ustalić właściwość wzrostu wielobiegunowego. Taki towarzyszący jest taki sam, jak konkretna mapa równoważna z twojego ulubionego modelu dla nieredukowalnej reprezentacji do algebry wielomianowej w zmiennych (Grochow nazywa to modułem oddzielającym ). Niezmienni teoretycy z XIX wieku mieli dwie metody generowania takich obiektów: teorię eliminacji i algebrę schematyczną .$F_2$$m$$G$$\lambda$$n^2$$X$

Bardzo przykład, w którym i są binarnymi formami pod działaniem (patrz to pytanie MO ), mówi i Oddzielający towarzyszący (tutaj w rzeczywistości kowariant) jest Hesjanem ogólnego binarnego kwartalnego Znika (identycznie w ) dla ale nie dla$F_1$$F_2$$G=SL(2)$

$$F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4$$ $$F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ .$$ $F$ $$H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ .$$ $x,y$$F=F_1$$F=F_2$. W tym przypadku Hesjan może być postrzegany jako mapa ekwiwariantna z nieredukowalnej podanej przez drugą potęgę symetryczną (podstawowej dwuwymiarowej reprezentacji) do pierścienia współrzędnych dla afinicznej przestrzeni kwantyków binarnych.

Zatem ewentualny superoptymistyczny „plan” dla GCT obejmuje następującą sekwencję kroków.

1) Znajdź sposób na wygenerowanie ton towarzyszących.

2) Zidentyfikuj wyraźnych kandydatów do zniknięcia na i udowodnij tę własność.$F_1$

3) Pokaż, że nie znikają na .$F_2$

Etap 1) jest w zasadzie rozwiązany w Pierwszym Podstawowym Twierdzeniu dla ale istnieje rozbieżność: wyznacznikiem jest naturalny obiekt w niezmiennej teorii dla (działający na wierszach i kolumny) zamiast . Można spróbować naprawić niedopasowanie, wyrażając podstawowy blok konstrukcyjny niezmiennej teorii w kategoriach jednego dla (zobacz to pytanie MO dotyczące podobnego problemu redukcji od do ).$GL(n^2)$$GL(n)\times GL(n)$$GL(n^2)$$GL(n^2)$$GL(n)\times GL(n)$$SL(n(n+1)/2)$$SL(n)$

Zgadywanie odpowiednich kandydatów do kroku 2) jest dla mnie trudne. Wiedząc wcześniej, że niektóre krotności są niezerowe, zdecydowanie by pomogło. Chociaż można odłożyć na później i odroczyć dowód nieidentycznego zniknięcia towarzyszącego kroku 3), który i tak powinien wykazać więcej. Jeśli ktoś ma takich właściwych kandydatów, pokazanie, że znikają na może być łatwe dzięki argumentom, które można nazwać zasadą wykluczenia Pauliego (kurczenie się symetryzacji z antysymetrizacją), wysoką wartością liczby chromatycznej lub po prostu „brakiem przestrzeni”.${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$$F_1$

Myślę jednak, że najtrudniejszą częścią jest krok 3). Na przykład w mojej pracy „16 051 formuł dla niezmiennika sześciennego potrójnego Ottaviani” z Ikenmeyer i Royle zgadywania dokonano za pomocą wyszukiwania komputerowego, ale z właściwym kandydatem w dłoni zniknięcie na było stosunkowo łatwe do wyjaśnienia (to raczej ładny przykład liczby chromatycznej ze względu na globalne właściwości wykresu zamiast jakiejś dużej kliki). Analogia do kroku 3) w naszym artykule została wykonana na podstawie obliczeń komputerowych z użyciem siły brutalnej i nadal nie mamy pojęcia, dlaczego jest to prawda. Paradygmatycznym problemem związanym z krokiem 3) jest przypuszczenie Alon-Tarsi (patrz to pytanie MO i to$F_1$też). Moim zdaniem, należy poczynić postępy w tego rodzaju pytaniach ( Twierdzenie Czterech Kolorów jest również tego rodzaju, poprzez redukcję spowodowaną przez Kauffmana i Bar-Natana) przed hipotezą Valianta.

Ponieważ pytanie dotyczy przełomów w GCT. Myślę, że ten artykuł autorstwa Landsberga i Ressayre'a również zasługuje na uwagę, ponieważ sugeruje, że rozsądne domysły dla dokładnej wartości to Należy zauważyć, że Bürgisser i Ikenmeyer w tym artykule przedstawili dowód koncepcji jednoznacznego podejścia „Krok 1), 2), 3)” dotyczący znacznie prostszego problemu . Na koniec, aby uzyskać więcej informacji na temat GCT, bardzo polecam recenzję „Teoria złożoności geometrycznej: wprowadzenie do geometrów” autorstwa Landsberga.$c(m)$

$$\left(\begin{array}{c}2m\\ m \end{array}\right)-1\ .$$

PS: Powinienem dodać, że mój pesymizm jest specyficzny dla Odważnej Hipotezy, która jest „hipotezą Riemanna” w tej dziedzinie. Oczywiście nie należy wylewać dziecka z kąpielą i oczerniać GCT, ponieważ jak dotąd nie udowodniono tego przypuszczenia. Istnieje wiele bardziej dostępnych problemów w tej dziedzinie, w której poczyniono postępy i oczekuje się dalszych postępów. Zobacz w szczególności wyżej wymieniony artykuł Grochowa i recenzję Landsberga.

GCT to program badawczy mający udowodnić granice teorii złożoności i poniekąd przeciwstawia się streszczenie / podsumowaniu w stylu wikipedii z powodu jego dużej abstrakcji, ale dla tłumu TCS dostępne są dobre ankiety. [2] [3] [4] (i z pewnością Wikipedia jest najlepszym miejscem dla wpisów na Wikipedii). został sformułowany na początku 2000 roku przez Mulmuleya i jest zarówno stosunkowo nowy w teorii złożoności, jak i bardzo zaawansowany, wykorzystując i stosując zaawansowaną matematykę (geometria algebraiczna), która nie powstała w teorii TCS / złożoności.

podejście to jest uważane przez niektóre władze za obiecujące, ale być może zbyt skomplikowane, tzn. nie zostało udowodnione i dlatego jest kontrowersyjne, czy mogłoby pokonać standardowe znane „bariery”. (w tym sensie wykazuje pewne oznaki tak zwanego „kuhniańskiego„ przesunięcia paradygmatu ”). Nawet Mulmuley sugeruje, że po dziesięcioleciach dalszego rozwoju może realistycznie nie odnieść sukcesu (w dowodzeniu dużych podziałów klas złożoności). oto sceptyczna opinia Fortnowa, wiodącego autorytetu w dziedzinie teorii złożoności: [1]

Zastanów się nad wielką górą, a chcesz dotrzeć na szczyt góry. Nadchodzi Ketan i mówi, że nauczy Cię, jak tworzyć narzędzia potrzebne do wspinaczki na górę. Zajmie to ciężki miesiąc nauki, a te narzędzia nie są wystarczająco dobre, aby wspiąć się na górę. Muszą zostać ulepszone, a te ulepszenia nie będą miały miejsca za twojego życia. Ale czy nie chcesz się dowiedzieć, jak inni będą teraz wspinać się po górach?

[1] Jak udowodnić, że NP różni się od bloga P Fortnow

[2] Zrozumienie podejścia Mulmuley-Sohoni do P vs. NP Regan

[3] O P vs. NP i teorii złożoności geometrycznej Mulmuley

[4] Program GCT w kierunku problemu P vs. NP Mulmuley