Konstruktivität in natürlichem Beweis und geometrischer Komplexität

Kürzlich hat Ryan Willams bewiesen, dass Konstruktivität in natürlichem Beweis unvermeidbar ist, um eine Trennung der Komplexitätsklassen abzuleiten: und . T C $\mathsf{NEXP}$$\mathsf{TC}^{0}$

Die Konstruktivität in Natural Proof ist eine Bedingung, die alle kombinatorischen Beweise in auf die Schaltungskomplexität erfüllen, und dass wir durch einen ausgeführten Algorithmus entscheiden können, ob die Zielfunktion in (oder einer anderen "harten" Komplexitätsklasse) eine "harte" Eigenschaft hat in Poly-Zeit in der Länge der Wahrheitstabelle der Zielfunktion.$\mathsf{NEXP}$

Die beiden anderen Bedingungen sind: Nutzlose Bedingungen, die eine "harte" Eigenschaft erfordern, können nicht von Schaltkreisen in berechnet werden.$\mathsf{TC}^0$

Meine Frage ist :

Stellt dieses Ergebnis die Geometrische Komplexitätstheorie (GCT) nicht zur Verfügung, um Haupttrennungsprobleme wie vs , vs oder vs zu ?N P P N C N E X P T C$\mathsf{P}$$\mathsf{NP}$$\mathsf{P}$$\mathsf{NC}$$\mathsf{NEXP}$$\mathsf{TC}^0$

Verweise:

• Ryan Williams, " Natural Proofs Versus Derandomization "

Nein, die Unvermeidbarkeit der Konstruktivität lässt die GCT definitiv immer noch als tragfähigen Angriffsplan für Probleme im unteren Bereich wie $NP$ vs. offen $P/poly$.

Zunächst ist zu erwähnen, dass Ryans Konstruktivitätsergebnis den sogenannten "Flip Theorems" von Mulmuley sehr ähnlich ist. Diese besagen zum Beispiel, dass es eine gibt, wenn permanent keine arithmetischen Schaltkreise mit Polygröße hat randomisierte polyzeitkonstruierbare Menge von (polynomiell vielen) Matrizen so dass sich jede kleine Schaltung von der bleibenden auf einer dieser Matrizen unterscheidet. Siehe Explicit Proofs and The Flip, Technischer Bericht, Fakultät für Informatik, Universität Chicago, September 2010, von Mulmuley.$\{M_1, \dotsc, M_{p(n)}\}$

Zweitens ist die (bereits von Siuman erwähnte) zentrale Bedeutung der Symmetrie-Charakterisierung in der GCT seit Regans Umfrage deutlicher geworden. Wenn sich herausstellt, dass die Symmetrie-Charakterisierung für GCT so entscheidend ist, wie es scheint, dann kommt dies bereits um den Zustand der Größe herum. Zur Definition der Symmetriecharakterisierung siehe diese Antwort auf eine eng verwandte frühere Frage .

Zum Beweis, dass Symmetriecharakterisierung gegen die Größe verstößt, siehe Abschnitt 3.4.3 "Symmetriecharakterisierung vermeidet die Razborov-Rudich-Barriere" in meiner Dissertation (schamlose Selbstpfropfen, aber ich weiß nirgendwo anders, wo dies so vollständig niedergeschrieben ist). . Ich vermute, dass es auch gegen die Konstruktivität verstößt, habe das aber als offene Frage dort gelassen. (Weiter oben in Kapitel 3 finden Sie auch eine Übersicht über die Flip-Theoreme in GCT und deren Beziehung zur Symmetrie-Charakterisierung.)

(Ich finde es interessant, dass die Symmetrie-Charakterisierung - genau die Eigenschaft, von der wir vermuten, dass sie in der GCT verwendet wird, die Razborov - Rudich umgeht - verwendet wird, um die Flip-Theoreme zu beweisen, die im Wesentlichen besagen, dass Konstruktivität notwendig ist.)

Schließlich ist es erwähnenswert , dass , obwohl in den langfristig GCT Zielen Adresse im Vergleich zu P / p o l y und anderen Boolesche Problemen, im Moment der meisten Arbeiten in GCT auf algebraischen Analoga davon fokussiert ist, wie zum Beispiel über die Anlage Zahlen, und es gibt noch kein algebraisches Analogon von Rasborow - Ruditsch (das ich kenne).$NP$$P/poly$

$NEXP \not\subset TC^0$$NEXP \cap coNEXP \not\subset ACC$

$P$$NP$

Ein paar weitere Kommentare dazu: Die Beziehung zwischen GCT und Natural Proofs wurde in der Vergangenheit diskutiert (sogar in den Originalarbeiten von GCT selbst). Während es keinen Konsens darüber zu geben scheint, welche "Konstruktivität" oder "Größe" durch den GCT-Ansatz verletzt werden würde, argumentierten Mulmuley und Sohoni an einem Punkt, dass wenn GCT durchgeführt werden könnte, dies die Größe verletzen sollte. Eine relevante Referenz finden Sie in Abschnitt 6 von Regans Übersicht über GCT . Ich möchte jedoch hinzufügen, dass diese Übersicht bereits 10 Jahre alt ist und seitdem viel Arbeit in die GCT geflossen ist. Ich bin mir nicht sicher, ob es eine überarbeitete / neue Meinung dazu gibt. (Vielleicht kann Josh Grochow einschalten?)

Die kurze Antwort lautet Nein .

Der Ansatz der Geometrischen Komplexitätstheorie zielt auf bestimmte extrem seltene Eigenschaften ab, von denen Mulmuley behauptet, dass sie nicht "groß" sind, wie von Rasborow und Ruditsch definiert. Für ein formelles Argument siehe auch Joshua Grochows These , Abschnitt 3.4.3 Symmetrie-Charakterisierung vermeidet die Razborov-Rudich-Barriere , und seine Antwort .

Der folgende Absatz stammt aus On P vs. NP und Geometric Complexity Theory von Ketan Mulmuley ( JACM 2011 oder Manuskript ), Abschnitt 4.3 A High Level Plan :

Ziel ist es, diese Schritte explizit durchzuführen und dabei die Charakterisierung durch Symmetrien von Permanent und Determinante auszunutzen. Wir werden später spezifizieren, was ausdrücklich bedeutet; vgl. Hypothese 4.6. Dieser Ansatz ist insofern extrem starr, als er nur für extrem seltene harte Funktionen funktioniert, die durch ihre Symmetrien gekennzeichnet sind. Diese extreme Steifheit ist viel mehr als nötig, um die Barriere gegen natürliche Beweise zu umgehen [Razborov und Rudich 1997].

Da sowohl die Bedingungen der Konstruktivität als auch der Größe für einen natürlichen Beweis erforderlich sind (wo der Nutzen impliziert ist), reicht der Nachweis, dass die Konstruktivität unvermeidbar ist, nicht aus, um solche Ansätze auszuschließen (obwohl dies ein großer Fortschritt ist).