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

25

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 0NEXPTC0

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.NEXP

Die beiden anderen Bedingungen sind: Nutzlose Bedingungen, die eine "harte" Eigenschaft erfordern, können nicht von Schaltkreisen in berechnet werden.TC0

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 0PNPPNCNEXPTC0

Verweise:

Auyun
quelle

Antworten:

20

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.{M1,,Mp(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).NPP/pOly

Joshua Grochow
quelle
4
Josh: Mein dürftiges Verständnis ist, dass die Ergebnisse von Mulmuley in der Form "Permanent hat keine Polysize-Schaltkreise impliziert Polynom-Zeit-Hindernisse für Permanent" auch eine zusätzliche Derandomisierungshypothese erfordern, beispielsweise für PIT. (Aber es ist eine interessante Frage: Ist eine solche Derandomisierungshypothese überhaupt erforderlich, wenn wir bereits davon ausgehen, dass die Permanente keine kleinen Schaltkreise hat?) Vielen Dank für den Hinweis auf Ihre These!
Ryan Williams
1
@ RyanWilliams: Ja, das ist richtig. Ich aktualisiere die Antwort jetzt und sage "randomisierte Polyzeit".
Joshua Grochow
17

NEXPTC0NEXPcONEXPEINCC

PNP

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?)

Ryan Williams
quelle
14

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).

Siuman
quelle