[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 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 ∈ G(Af)(x1,...,xm)=f(A−1(x1),...,A−1(xm))A∈GLmx1,...,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)={A∈GLm:Af=f}ff′mfAf′=f′A∈Stab(f)f′f
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.
źródło