Wie vermeidet der geometrische Ansatz von Mulmuley-Sohoni zur Erzeugung von Untergrenzen die Erzeugung natürlicher Beweise (im Sinne von Razborov-Rudich)?

Die genaue Formulierung des Titels stammt von Anand Kulkarni (der die Erstellung dieser Website vorgeschlagen hat). Diese Frage wurde als Beispielfrage gestellt, aber ich bin wahnsinnig neugierig. Ich weiß sehr wenig über algebraische Geometrie und verstehe die Hindernisse in der Frage P / Poly versus NP tatsächlich nur flüchtig. (Nicht relativierend, nicht algebraisch, wahrscheinlich kein natürlicher Beweis.) .

Wie kommt es, dass die algebraische Geometrie diese Art von Hindernissen umgehen kann? Handelt es sich nur um eine Feldexperten-Intuition, oder haben wir einen guten Grund zu der Annahme, dass der Ansatz grundlegend leistungsfähiger ist als frühere Ansätze? Welche schwächeren Ergebnisse konnte dieser Ansatz erzielen?

[Ich beantworte die Frage wie im Titel angegeben und lasse die Litanei anderer Fragen zu GCT für andere Threads übrig.] Wenn die in GCT auftretenden Vermutungen bewiesen werden, scheint dies die Tatsache entscheidend zu nutzen, dass die betrachteten Funktionen (determinant und permanent) und andere verwandte Polynome für P / poly und NP) sind durch ihre Symmetrien charakterisiert. Diese Notwendigkeit ist kein formelles Ergebnis, sondern eine von mehreren Experten zum Ausdruck gebrachte Intuition. (Grundsätzlich ist es weitaus schwieriger, die entstehende algebraische Geometrie und Darstellungstheorie zu verstehen, wenn keine Charakterisierung durch Symmetrien erfolgt.)

Dies sollte Razborov-Rudich umgehen, da nur sehr wenige Funktionen durch ihre Symmetrie gekennzeichnet sind (unter Umgehung der Größe bei der Definition von natürlichen Beweisen). Auch hier habe ich keinen Beweis dafür gesehen, aber es ist eine Intuition, die ich von mehreren Experten gehört habe.

Bei den komplexen Zahlen ist mir nicht klar, dass es ein Analogon von Rasborow-Ruditsch gibt. Obwohl sich der Großteil der GCT derzeit auf die komplexen Zahlen konzentriert, gibt es Analoga in der endlichen Eigenschaft (versprochen in der bevorstehenden Veröffentlichung GCT VIII). In endlichen Merkmalen könnte man tatsächlich eine Aussage der Form "Nur sehr wenige Funktionen zeichnen sich durch ihre Symmetrien aus" nachweisen.

[Als Antwort auf Ross Sniders Kommentar folgt eine Erklärung der Charakterisierung durch Symmetrien.]

Zunächst eine beispielhafte Erklärung. Definieren Sie für das Beispiel eine Hilfsfunktion . Wenn A eine Permutationsmatrix, dann q ( A ) = 1 und wenn A diagonal ist , dann q ( A ) = d e t ( A ) (Produkt der diagonalen Einträge). Nehmen wir nun an, p ( X ) sei ein homogenes Grad- n- Polynom in n 2 -Variablen (die wir als die Entire einer n × n- Matrix $q$$A$$q(A)=1$$A$$q(A)=det(A)$$p(X)$$n$$n^2$$n \times n$$X$). Wenn die folgenden Symmetrien hat:$p$

• (transponieren)$p(X) = p(X^t)$
• für alle Paare von Matrizen ( A , B ), so dass A und B entweder Permutationsmatrizen oder Diagonalmatrizen sind und q ( A ) q ( B ) = $p(AXB) = p(X)$$(A,B)$$A$$B$$q(A)q(B) = 1$

dann ist ein konstantes Vielfaches von p e R m ( X ) für alle Matrizen X . Daher sagen wir, dass die bleibende Kraft durch ihre Symmetrien gekennzeichnet ist.$p(X)$$perm(X)$$X$

Ganz allgemein, wenn wir ein (homogenes) Polynom haben . . . , in m Variablen, dann G L m (die Gruppe aller invertierbaren m × m - Matrizen) auf f durch ( A f ) ( x 1 , . . . , x m ) = f ( A - 1 ( x 1 ) $f(x_1, ..., x_m)$$m$$GL_m$$m \times m$$f$ für A ∈ G L m (wo wir die Variablen einnehmen x 1 , . . . , X m als Basis für den m -dimensionalen Vektorraumauf der G L m natürlich wirkt). Der Stabilisator von f in G L m ist die Untergruppe 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$ . Wir sagen, f ist durch seine Symmetrien charakterisiert, wenn gilt: für jedes homogene Polynom f ' in m Variablen des gleichen Grades wie f , wenn A f ' = f ' für alle A ∈ Stab ( f ) , dann ist f ' a konstantes Vielfaches von f .$\text{Stab}(f) = \{ A \in GL_m : Af = f\}$$f$$f'$$m$$f$$Af' = f'$$A \in \text{Stab}(f)$$f'$$f$

Joshua Grochows Antwort ist gut, aber ich denke, es lohnt sich, eine allgemeinere Bemerkung zu machen. Die Razborov-Rudich Ergebnis sagt , dass , wenn Sie wollen beweisen , dass einige Boolesche Funktion ist nicht in , dann (vorausgesetzt , Sie ihre Verschlüsselungs Hypothese glauben) Sie irgendeine Eigenschaft dieser Funktion verwenden müssen , die entweder nicht - triviale zu berechnen ist oder das wird nur von einer kleinen Anzahl anderer Boolescher Funktionen geteilt. In der Praxis ist es nicht einfach, geeignete Eigenschaften zu finden. Die Beobachtung von Razborov-Rudich schließt jedoch nicht wirklich sehr viele allgemeine Angriffspläne auf Schaltungsuntergrenzen aus, da keine konkreten Einzelheiten über den beabsichtigten Beweis vorliegen. Nehmen wir zum Beispiel an, ich würde naiv sagen, dass ich meinen Plan beweisen will$P/poly$ involviertzeigendass S A T ∉ P / p o l y , und daß ich bestimmtdie Tatsache zu nutzendass S A T ist N P -komplette. Dieser naive „Angriffsplan“ ist fast inhaltsfrei, aber Razborov-Rudich ist es nicht auszuschließen, weil N P -completeness keine große Eigenschaft ist.$NP\not\subseteq P/poly$$SAT\notin P/poly$$SAT$$NP$$NP$

Anders ausgedrückt: Razborov-Rudich ist in den frühen Phasen der Planung einer Angriffslinie auf die unteren Grenzen der Rennstrecke in der Regel kein großes Hindernis, solange Sie in Ihrem Plan etwas Platz lassen, um eventuell "besondere Eigenschaften" einzusetzen. Ihrer Kandidaten Boolesche Funktionen. Erst wenn Sie die Ärmel hochkrempeln und versuchen, die Details des Arguments zu vervollständigen, wird die Einbürgerungsbarriere ernsthaft ihren Kopf nach hinten strecken. Da sich GCT noch in einem frühen Entwicklungsstadium befindet, sollten wir noch nicht damit rechnen, dass wir uns um die Einbürgerung große Sorgen machen müssen (obwohl es sich natürlich lohnt, zu prüfen, ob das GCT-Programm nicht aus trivialen Gründen zum Scheitern verurteilt ist).

Vielleicht möchten Sie auch Ken Regans Darstellung von GCT überprüfen , die einige Anmerkungen zur Einbürgerungsbarriere enthält.