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

31

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

Die Frage, die mich nervt:

Ist es möglich, mit GCT bekannte Separationen wie oder LP S P A C E anzuzeigen ?PEXPLPSPEINCE

Macht so etwas wie LPSPEINCE

  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 ?PNP
Mugizi Rwebangira
quelle
Joshs Kommentare zu diesem Beitrag scheinen zu implizieren, dass es möglich ist, eine solche Trennung in "GCT-Sprache" zu formulieren, aber es ist nicht trivial und noch ist niemand dazu gekommen. Würde mich aber trotzdem über einen Einblick von einem Experten freuen.
Mugizi Rwebangira
4
AFAIR, Mulmuley beginnt seine Präsentation ( video.ias.edu/stream&ref=226 ) mit #P vs NC als eine natürlichere Frage für GCT. Dies ist möglicherweise eine erste Eingebung für die Beantwortung Ihrer Frage.
Michaël Cadilhac
Danke für diesen Link Michaël. Aus irgendeinem Grund ist die Lautstärke zu niedrig, um sie auf meinem Bürodesktop anzuhören, aber ich werde es versuchen, wenn ich zu Hause bin. Obwohl Josh auf jeden Fall schon eine gute Antwort gegeben hat.
Mugizi Rwebangira

Antworten:

25

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 ,LP und E X P.PSPACEEXP

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

Ein vernünftiges Ziel könnte jedoch sein, mit GCT ein algebraisches Analogon von zu beweisen .FPFEXP

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 P auftretenFPFEXPPNPoder 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.FEXPFEXP

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 beweisen2×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 gebunden32n22unter 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 kann2×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 ≠ gelten zu können3×33×3 , sondern auch für unbekanntewie P ≠ zu geltenFPFEXP , wohingegen wir wissen, dass Diagonalisierung dies nicht tut.PNP

Joshua Grochow
quelle
9
Scheint verrückt, dass es so schwer sein sollte, zu tadeln ! FPFEXP
Ryan Williams
2
Danke dir! Das war sehr hilfreich. Meine allgemeine Idee (und ich denke auch die von anderen) war es, über einen "einfachen ersten Schritt" in diesem GCT-Programm nachzudenken. Aber es scheint wirklich keinen zu geben (zumindest bis jetzt). Sie haben erwähnt, dass der Ansatz der Grobner-Basen eine doppelt exponentielle Laufzeit hat. Wissen Sie, wie lange die (asymptotische) Suche nach Burgisser und Ikenmeyer gedauert hat?
Mugizi Rwebangira
3
Ich glaube, es war immer noch exponentiell (was teilweise erklärt, warum sie Landsbergs Ergebnis nicht ganz reproduzieren konnten), aber nur einfach exponentiell :).
Joshua Grochow
1
@JoshuaGrochow: Es wäre hilfreich, wenn Sie ein Update-Banner entweder am Anfang oder am Ende der Antwort platzieren würden. In meinem Alter sind meine Augen nicht mehr so ​​wie früher, und als ich die Antwort zum ersten Mal überflog, habe ich die Änderung verpasst.
Vijay D
14

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 AC0[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.

Robin Kothari
quelle