W jaki sposób podejście geometryczne Mulmuleya-Sohoniego do wytwarzania dolnych granic unika tworzenia naturalnych dowodów (w sensie Razborowa-Rudicha)?

22

Dokładne sformułowanie tytułu należy do Ananda Kulkarniego (który zaproponował utworzenie tej strony). To pytanie zostało zadane jako przykładowe, ale jestem niesamowicie ciekawy. Wiem bardzo mało o geometrii algebraicznej, a tak naprawdę posiadam jedynie pobieżne, licencjackie rozumienie przeszkód występujących w pytaniu P / poli kontra NP (brak relatywizacji, brak algebrazowania, prawdopodobnie nie będzie to naturalny dowód) .

Co sprawia, że ​​geometria algebraiczna może ominąć tego rodzaju przeszkody? Czy to tylko intuicja eksperta w terenie, czy mamy naprawdę dobry powód, by sądzić, że podejście jest zasadniczo silniejsze niż poprzednie? Jakie słabsze wyniki udało się osiągnąć dzięki temu podejściu?

Ross Snider
źródło

Odpowiedzi:

19

[Odpowiem na pytanie, jak podano w tytule, pozostawiając litanię innych pytań dotyczących GCT dla innych wątków.] Udowodnienie przypuszczeń powstałych w GCT wydaje się mieć zasadnicze znaczenie dla uwzględnienia rozważanych funkcji (determinujących i stałych, i inne pokrewne wielomiany dla P / poli i NP) charakteryzują się ich symetriami. Konieczność ta nie jest formalnym rezultatem, ale intuicją wyrażoną przez kilku ekspertów. (Zasadniczo, że przy braku charakteryzacji przez symetrie, zrozumienie powstałej geometrii algebraicznej i teorii reprezentacji jest znacznie trudniejsze.)

Powinno to ominąć Razborowa-Rudicha, ponieważ bardzo niewiele funkcji charakteryzuje się ich symetriami (pomijając warunek wielkości w definicji dowodów naturalnych). Ponownie nie widziałem na to dowodu, ale słyszałem intuicję wyrażoną przez kilku ekspertów.

Teraz, poza liczbami zespolonymi, nie jest dla mnie jasne, że istnieje analog Razborowa-Rudicha. Chociaż większość GCT koncentruje się obecnie na liczbach zespolonych, istnieją analogi w skończonej charakterystyce (obiecane w nadchodzącym artykule GCT VIII). W skończonej charakterystyce można faktycznie udowodnić zdanie o formie „Bardzo niewiele funkcji charakteryzuje się symetriami”.


[W odpowiedzi na komentarz Rossa Snidera, oto wyjaśnienie charakteryzacji przez symetrie.]

Najpierw wyjaśnienie na przykładzie. Na przykład zdefiniuj funkcję pomocniczą . Jeśli A jest macierzą permutacji, to q ( A ) = 1, a jeśli A jest diagonalna, to q ( A ) = d e t ( A ) (iloczyn pozycji przekątnych). Załóżmy teraz, że p ( x ) jest jednorodny stopień n wielomian n 2 zmiennych (to uważamy jak aplecie z o n × n macierzy XqAq(A)=1Aq(A)=det(A)p(X)nn2n×nX). Jeśli ma następujące symetrie:p

  • (transpozycja)p(X)=p(Xt)
  • dla wszystkich par macierzy ( A , B ) tak, że A i B są albo matrycami permutacyjnymi, albo macierzami diagonalnymi, a q ( A ) q ( B ) = 1p(AXB)=p(X)(A,B)ABq(A)q(B)=1

następnie jest stała wielokrotnością p e r m ( X ) dla wszystkich macierzy X . Dlatego mówimy, że to, co stałe, charakteryzuje się symetriami.p(X)perm(X)X

Mówiąc ogólnie, jeśli mamy (jednorodne) wielomianu w m zmiennych, a G L m (grupa wszystkich odwracania sygnału m x m matryce) działa na F w ( A f ) ( x 1 , . . . , x m ) = f ( - 1 ( x 1 ) ,f(x1,...,xm)mGLmm×mf dlaG L m (gdzie pacjent jest zmienne x 1 , . . . , X m , jako podstawa do m -wymiarowej przestrzeni wektorowej w którym G L m naturalnie działa). Stabilizatorem f w G L m jest podgrupa Stab ( f ) = { A G(Af)(x1,...,xm)=f(A1(x1),...,A1(xm))AGLmx1,...,xmmGLmfGLm . Mówimy, że f charakteryzuje się symetriami, jeśli zachowuje się następującą wartość: dla dowolnej jednorodnej wielomianu f ' wzmiennych m o tym samym stopniu co f , jeżeli A f = f dla wszystkich A Stab ( f ) , to f jest a stała wielokrotność f .Stab(f)={AGLm:Af=f}ffmfAf=fAStab(f)ff

Joshua Grochow
źródło
To wydaje się być świetną odpowiedzią, ale obawiam się, że nie rozumiem trochę symetrii funkcji (co oznacza, że ​​brakuje mi istotnych szczegółów odpowiedzi). Czy mógłbyś rozpakować, jaka jest symetria funkcji, dlaczego tak ważne jest, aby bardzo niewiele funkcji ją scharakteryzowało (aka - dlaczego pozwoliłoby to pominąć warunek wielkości Razborowa)? Dla jasności twoja odpowiedź jest taka, że ​​istnieje mieszanka. Są powody, dla których podejście to wygląda obiecująco, ale ostatecznie dowody z tych powodów są w dużej mierze spowodowane intuicją ekspertów.
Ross Snider
4
Dodałem dla ciebie wyjaśnienie charakteryzacji przez symetrie. Nawet jeśli jest tak, że bardzo niewiele funkcji charakteryzuje się symetriami, nadal polegamy na intuicji ekspertów, że charakteryzacja za pomocą symetrii będzie kluczowa dla udowodnienia przypuszczeń powstałych w GCT. Jeśli tak rzeczywiście jest, wówczas techniki dowodowe stosowane w tych przypuszczeniach działałyby tylko dla niewielkiej części funkcji, omijając w ten sposób warunek wielkości. (A może nie o to pytałeś?)
Joshua Grochow,
Ooooch Zapisane tutaj Święto Trzech Króli. Dzięki wielkie. Jak mogę nie zaakceptować tej odpowiedzi?
Ross Snider
15

P/polyS A T P / p o l y S A T N P N PNPP/polySATP/polySATNPNP

Innymi słowy, Razborov – Rudich zwykle nie stanowi dużej przeszkody we wczesnych etapach planowania linii ataku na dolne granice obwodu, o ile pozostawiasz miejsce w planie na ewentualne zastosowanie „specjalnych właściwości” swoich kandydujących funkcji boolowskich. Dopiero po podwinięciu rękawów i próbie wypełnienia szczegółów argumentu, że bariera naturalizacyjna zacznie poważnie odchylać głowę. Biorąc pod uwagę, że GCT jest wciąż na wczesnym etapie rozwoju, nie powinniśmy się jeszcze martwić o naturalizację (choć oczywiście warto sprawdzić, czy program GCT nie jest skazany na trywialne powody).

Możesz także zapoznać się z ekspozycją GCT Kena Regana , która zawiera kilka uwag na temat bariery naturalizacyjnej.

Timothy Chow
źródło