Jak trudno jest zastosować podejście GCT Mulmuley-Sohoni do pokazania * znanych * separacji złożoności?

W tym poście Josh Grochow na blogu o złożoności relacjonuje ostatnie warsztaty poświęcone GCT, które odbyły się w lipcu w Princeton. Kilku uczestników argumentowało, że powinniśmy używać GCT do atakowania łatwiejszych problemów niż $\mathsf{P}$ vs. $\mathsf{NP}$ w celu zbudowania intuicji i sprawdzenia, czy metoda ma potencjał.

Pytanie, które mnie denerwuje:

Czy można użyć GCT do pokazania znanych separacji, takich jak $\mathsf{P} \neq \mathsf{EXP}$ lub $\mathsf{L} \neq \mathsf{PSPACE}$ ?

Czy coś takiego jak $\mathsf{L} \neq \mathsf{PSPACE}$

1. Nie ma to nawet sensu w kontekście GCT, ani
2. Jest całkowicie trywialny i nieciekawy w środowisku GCT, lub
3. Prowadzić do domysłów równie trudnych jak vs. N P ?$\mathsf{P}$$\mathsf{NP}$

Krótka odpowiedź: prawdopodobnie nie (1), zdecydowanie nie (2) i prawdopodobnie (3).

To jest coś, o czym myślałem od dłuższego czasu. Po pierwsze, w pewnym sensie GCT ma na celu raczej ograniczenie granic funkcji obliczeniowych niż problemów decyzyjnych. Ale twoje pytanie ma sens w wersjach klas funkcyjnych , P , P S P A C E i E X $L$$P$$PSPACE$$EXP$ .

Po drugie, faktycznie udowadnia wersje boolowskie - te, które znamy i kochamy, takie jak $FP \neq FEXP$ - jest prawdopodobnie niezwykle trudne w podejściu GCT, ponieważ wymagałoby to zastosowania modułowej teorii reprezentacji (teoria reprezentacji ponad skończoną pola), co nie jest dobrze rozumiane w żadnym kontekście.

Jednak rozsądnym celem może być użycie GCT do udowodnienia algebraicznego analogu $FP \neq FEXP$ .

Aby przejść do twojego pytania: Wierzę, że pytania te można sformułować w kontekście GCT, choć nie od razu wiadomo, jak to zrobić. Mniej więcej potrzebujesz funkcji, która jest kompletna dla klasy i charakteryzuje się symetriami; dodatkowy bonus, jeśli teoria reprezentacji związana z funkcją jest łatwa do zrozumienia, ale ta ostatnia jest zwykle dość trudna.

Nawet gdy pytania zostaną sformułowane w kontekście GCT, nie mam pojęcia, jak trudno będzie użyć GCT do udowodnienia (algebraiczne analogi) itp. Teoretyczne wyobrażenia, które pojawią się w tych kontekstach najprawdopodobniej będzie miał bardzo podobny smak do tych powstających w P vs N $FP \neq FEXP$$P$$NP$lub wyznacznik permanentny vs. Można mieć nadzieję, że klasyczne dowody tych wyników separacji mogą dać pojęcie o tym, jak znaleźć teoretyczne „przeszkody” reprezentacyjne potrzebne do potwierdzenia GCT. Jednak dowody wspomnianych przez ciebie twierdzeń to wszystkie twierdzenia hierarchiczne oparte na diagonalizacji i nie widzę, w jaki sposób diagonalizacja naprawdę da ci wgląd w teorię reprezentacji związaną z funkcją, która jest kompletna dla (algebraicznego analogu) Powiedzmy X P. Z drugiej strony nie widziałem jeszcze, jak sformułować F E X $FEXP$$FEXP$ w kontekście GCT, więc jest trochę za wcześnie na powiedzenie.

Wreszcie, jak wspomniałem w tym poście na blogu, Peter Burgisser i Christian Ikenmeyer próbowali ponownie udowodnić dolną granicę granicy granicznej mnożenia macierzy (którą Joseph Landsberg udowodnił jako 7). Byli w stanie wykazać, że granica wynosi co najmniej 6, dzięki komputerowemu poszukiwaniu przeszkód w GCT. Aktualizacja kwietnia 2013 r . : od tego czasu udało im się ponownie udowodnić wynik Landsberga za pomocą niedrożności GCT i wykazać asymptozę 3$2 \times 2$dolna granica mnożenia macierzy$\frac{3}{2}n^2 - 2$przy użyciu takich przeszkód. Chociaż GCT nie odtworzył do tej pory znanego dolnegolimitumnożenia macierzy, umożliwia wyszukiwanie komputerowe bardziej wydajne niż alternatywa (która obejmowałaby zasady Grobnera, w najgorszym przypadku czas podwójnie wykładniczy). W swoich rozmowach podczas warsztatów zarówno Peter, jak i Christian wskazali (słusznie, powiedziałbym), że tak naprawdę mamy nadzieję, że uzyskamy obliczenie małych przykładów, nie jest potwierdzeniem znanych dolnych granic, ale pewienwgląd, który pozwoli nam je wykorzystać techniki sprawdzanianowychdolnych granic.

Zaletą GCT w kontekście mnożenia macierzy jest to, że technika łatwo uogólnia od mnożenia macierzy do 3 × 3 (chociaż obliczanie przeszkód za pomocą obecnych technik jest oczywiście droższe), podczas gdy podejście Landsberga wydaje się bardzo trudne do wdrożenia nawet w przypadku 3 × 3 . Podobną rzecz można powiedzieć o wspomnianych separacjach klas złożoności: GCT jest na tyle ogólny, że może mieć zastosowanie nie tylko do znanych wyników, takich jak F P ≠ F E X P , ale także do nieznanych, takich jak P $2 \times 2$$3 \times 3$$3 \times 3$$FP \neq FEXP$ , podczas gdy wiemy, że diagonalizacja nie.$P \neq NP$

Jest nowy artykuł na temat arXiv autorstwa Joshua Grochow , który pokazuje, jak umieścić kilka znanych niższych technik w ramce GCT i wydaje się, że nieco odpowiada na twoje pytanie.

(Jest to głównie komentarz, ale nikt go nie zauważy, więc zamieszczam go jako odpowiedź).

Ujednolicenie i uogólnienie znanych dolnych granic za pomocą teorii złożoności geometrycznej

Joshua A. Grochow

$AC^0[p]$przy czym jest to naturalne zjednoczenie i szerokie uogólnienie znanych wyników. Pokazuje również, że struktura GCT jest co najmniej tak potężna jak znane metody, i daje wiele nowych dowodów koncepcji, że GCT może rzeczywiście zapewnić znaczące asymptotyczne dolne granice. Ten nowy punkt widzenia otwiera również możliwość owocnych dwustronnych interakcji między wcześniejszymi wynikami a nowymi metodami GCT; przedstawiamy kilka konkretnych sugestii takich interakcji. Na przykład teoretyczny punkt widzenia GCT w naturalny sposób zapewnia nowe właściwości do rozważenia w poszukiwaniu nowych dolnych granic. Ten nowy punkt widzenia otwiera również możliwość owocnych dwustronnych interakcji między wcześniejszymi wynikami a nowymi metodami GCT; przedstawiamy kilka konkretnych sugestii takich interakcji. Na przykład teoretyczny punkt widzenia GCT w naturalny sposób zapewnia nowe właściwości do rozważenia w poszukiwaniu nowych dolnych granic. Ten nowy punkt widzenia otwiera również możliwość owocnych dwustronnych interakcji między wcześniejszymi wynikami a nowymi metodami GCT; przedstawiamy kilka konkretnych sugestii takich interakcji. Na przykład teoretyczny punkt widzenia GCT w naturalny sposób zapewnia nowe właściwości do rozważenia w poszukiwaniu nowych dolnych granic.