Wie schwierig ist es, mit dem Mulmuley-Sohoni-GCT-Ansatz * bekannte * Komplexitätstrennungen aufzuzeigen?

In diesem Gastbeitrag von Josh Grochow im Weblog zu Komplexität berichtet er über einen kürzlich in Princeton im Juli abgehaltenen Workshop zum Thema GCT. Einige der Teilnehmer argumentierten, dass wir GCT verwenden sollten, um leichtere Probleme als vs. N P anzugreifen , um Intuition aufzubauen und zu sehen, ob die Methode Potenzial hat.$\mathsf{P}$$\mathsf{NP}$

Die Frage, die mich nervt:

Ist es möglich, mit GCT bekannte Separationen wie oder L ≠ P S P A C E anzuzeigen ?$\mathsf{P} \neq \mathsf{EXP}$$\mathsf{L} \neq \mathsf{PSPACE}$

Macht so etwas wie $\mathsf{L} \neq \mathsf{PSPACE}$

1. Nicht einmal im GCT-Kontext sinnvoll, oder
2. Ist völlig trivial und uninteressant in GCT-Framework, oder
3. Zu Vermutungen führen, die genauso schwer sind wie gegen N P ?$\mathsf{P}$$\mathsf{NP}$

Kurze Antwort: wahrscheinlich nicht (1), definitiv nicht (2) und möglicherweise (3).

Dies ist etwas, worüber ich schon eine Weile nachgedacht habe. Erstens zielt GCT in gewissem Sinne darauf ab, die Rechenfunktionen zu begrenzen, anstatt Entscheidungsprobleme zu lösen. Aber Ihre Frage ist für die Funktionsklassenversionen von , P ,$L$$P$ und E X P.$PSPACE$$EXP$

Zweitens ist es in einem GCT-Ansatz wahrscheinlich unglaublich schwierig , tatsächlich die booleschen Versionen zu beweisen - die wir kennen und lieben, wie -, da dies die Verwendung einer modularen Darstellungstheorie erfordern würde (Darstellungstheorie über endlich) Felder), die in keinem Zusammenhang gut verstanden wird. $FP \neq FEXP$

Ein vernünftiges Ziel könnte jedoch sein, mit GCT ein algebraisches Analogon von zu beweisen .$FP \neq FEXP$

Um auf Ihre Frage zu kommen: Ich glaube, dass diese Fragen in einem GCT-Kontext formuliert werden können, obwohl es nicht sofort offensichtlich ist, wie. Mehr oder weniger benötigen Sie eine Funktion, die für die Klasse vollständig ist und sich durch ihre Symmetrien auszeichnet. Zusätzlicher Bonus, wenn die mit der Funktion verbundene Darstellungstheorie leicht zu verstehen ist, aber letztere normalerweise recht schwierig ist.

Selbst wenn die Fragen einmal in einem GCT-Kontext formuliert sind, weiß ich nicht, wie schwierig es sein wird, mit GCT (algebraische Analoga von) usw. zu beweisen . Die darstellungstheoretischen Vermutungen, die in diesen Kontexten entstehen werden wird wahrscheinlich einen sehr ähnlichen Geschmack haben wie diejenigen, die in P vs N $FP \neq FEXP$$P$$NP$oder permanent vs determinant. Man könnte hoffen, dass die klassischen Beweise dieser Trennungsergebnisse eine Vorstellung davon geben, wie man die repräsentationstheoretischen "Hindernisse" findet, die für einen GCT-Beweis benötigt werden. Allerdings sind die Beweise für die Aussagen , die Sie erwähnen alle Hierarchiesätze auf diagonalization basiert, und ich sehe nicht , wie diagonalization werden Sie wirklich viel Einblick in die Darstellungstheorie mit einer Funktion zugeordnet geben , die für (die algebraische Analogon von) abgeschlossen ist , sag. Andererseits habe ich noch nicht gesehen, wie man F E X P in einem GCT-Kontext formuliert , also ist es ein wenig früh zu sagen.$FEXP$$FEXP$

Schließlich haben Peter Burgisser und Christian Ikenmeyer, wie ich in diesem Blogbeitrag erwähnte, versucht, die Untergrenze des Grenzwerts von 2 × 2 erneut zu beweisen$2 \times 2$ Matrixmultiplikation (die 2006 von Joseph Landsberg als 7 nachgewiesen wurde) erneut zu beweisen. Sie konnten durch eine Computersuche nach GCT-Hindernissen nachweisen, dass der Grenzrang mindestens 6 beträgt. Update April 2013 : Seitdem ist es ihnen gelungen, Landsbergs Ergebnis mit einem GCT-Hindernis nachzuweisen und eine asymptotische 3 zu zeigen niedriger auf Matrizenmultiplikation gebunden$\frac{3}{2}n^2 - 2$unter Verwendung eines solchen Verstopfungen. Obwohl GCT die bekannte Untergrenze der Matrixmultiplikation bisher nicht reproduzierthat, ermöglicht es eine effizientere Computersuche als die Alternative (die Grobner-Basen beinhalten würde, die im schlimmsten Fall eine doppelt exponentielle Zeit sind). In ihren Gesprächen während des Workshops haben sowohl Peter als auch Christian darauf hingewiesen (richtig, würde ich sagen), dass das, was wir wirklich hoffen, wenn wir kleine Beispiele berechnen, nicht die bekannten Untergrenzen bestätigt, sondern einigeEinsichten, die es uns ermöglichen werden, diese zu nutzen Techniken zum NachweisneuerUntergrenzen.

Das Schöne an GCT im Zusammenhang mit der Matrixmultiplikation ist, dass die Technik leicht von auf 3 verallgemeinert werden kann$2 \times 2$ Matrixmultiplikationwerden kann (obwohl die Berechnung der Hindernisse mit den aktuellen Techniken offensichtlich teurer wird), während Landsbergs Ansatzsehrschwierig zu implementierenscheintauch für den 3 × 3 Fall. Ähnliches gilt für die von Ihnen erwähnten Komplexitätsklassentrennungen: GCT ist allgemein genug, um nicht nur für bekannte Ergebnisse wie F P $3 \times 3$$3 \times 3$ , sondern auch für unbekanntewie P $FP \neq FEXP$ , wohingegen wir wissen, dass Diagonalisierung dies nicht tut.$P \neq NP$

Es gibt einen neuen Artikel über arXiv von Joshua Grochow , in dem gezeigt wird, wie mehrere bekannte Techniken der unteren Schranke in das GCT-Framework eingefügt werden können, und der Ihre Frage anscheinend etwas beantwortet.

(Dies ist meistens nur ein Kommentar, aber niemand würde einen Kommentar bemerken, also poste ich ihn als Antwort.)

Vereinheitlichung und Verallgemeinerung bekannter Untergrenzen mittels geometrischer Komplexitätstheorie

Joshua A. Grochow

Wir zeigen, dass die meisten arithmetischen Schaltkreisuntergrenzen und Beziehungen zwischen Untergrenzen auf natürliche Weise in das von der geometrischen Komplexitätstheorie (GCT) vorgeschlagene repräsentationstheoretische Gerüst passen, einschließlich: der Technik partieller Ableitungen (Nisan-Wigderson), der Ergebnisse von Razborov und Smolensky auf $AC^0[p]$wodurch es eine natürliche Vereinheitlichung und breite Verallgemeinerung bekannter Ergebnisse ist. Es zeigt auch, dass der Rahmen der GCT mindestens so leistungsfähig ist wie bekannte Methoden, und es gibt viele neue Proof-of-Concept-Beweise, dass die GCT tatsächlich signifikante asymptotische Untergrenzen liefern kann. Dieser neue Standpunkt eröffnet auch die Möglichkeit fruchtbarer wechselseitiger Wechselwirkungen zwischen früheren Ergebnissen und den neuen Methoden der GCT. Wir liefern einige konkrete Vorschläge für solche Wechselwirkungen. Beispielsweise bietet der vertretungstheoretische Standpunkt von GCT natürlich neue Eigenschaften, die bei der Suche nach neuen Untergrenzen berücksichtigt werden müssen. Dieser neue Standpunkt eröffnet auch die Möglichkeit fruchtbarer wechselseitiger Wechselwirkungen zwischen früheren Ergebnissen und den neuen Methoden der GCT. Wir liefern einige konkrete Vorschläge für solche Wechselwirkungen. Beispielsweise bietet der vertretungstheoretische Standpunkt von GCT natürlich neue Eigenschaften, die bei der Suche nach neuen Untergrenzen berücksichtigt werden müssen. Dieser neue Standpunkt eröffnet auch die Möglichkeit fruchtbarer wechselseitiger Wechselwirkungen zwischen früheren Ergebnissen und den neuen Methoden der GCT. Wir liefern einige konkrete Vorschläge für solche Wechselwirkungen. Beispielsweise bietet der vertretungstheoretische Standpunkt von GCT natürlich neue Eigenschaften, die bei der Suche nach neuen Untergrenzen berücksichtigt werden müssen.