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

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?

[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 $q$$A$$q(A)=1$$A$$q(A)=det(A)$$p(X)$$n$$n^2$$n \times n$$X$). Jeśli ma następujące symetrie:$p$

• (transpozycja)$p(X) = p(X^t)$
• dla wszystkich par macierzy ( A , B ) tak, że A i B są albo matrycami permutacyjnymi, albo macierzami diagonalnymi, a q ( A ) q ( B ) = $p(AXB) = p(X)$$(A,B)$$A$$B$$q(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(x_1, ..., x_m)$$m$$GL_m$$m \times m$$f$ dla ∈ G 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 ∈ $(Af)(x_1,...,x_m) = f(A^{-1}(x_1),...,A^{-1}(x_{m}))$$A \in GL_m$$x_1,...,x_m$$m$$GL_m$$f$$GL_m$ . 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 .$\text{Stab}(f) = \{ A \in GL_m : Af = f\}$$f$$f'$$m$$f$$Af' = f'$$A \in \text{Stab}(f)$$f'$$f$

$P/poly$S A T ∉ P / p o l y S A T N P N $NP\not\subseteq P/poly$$SAT\notin P/poly$$SAT$$NP$$NP$

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.