Wikipedia-artige Erklärung der Geometrischen Komplexitätstheorie

Kann jemand eine kurze Erklärung für Mulmuleys GCT-Ansatz liefern, die auch für Laien verständlich ist? Eine Erklärung, die für eine Wikipedia-Seite zum Thema geeignet wäre (die im Moment stumm ist).

Motivation: Ich "lese" Scott Aaronsons Buch "Quantum Computing since Democritus" zusammen mit einem Freund von mir, der in der Stringtheorie forscht. Im Vorwort des Buches nennt Aaronson GCT "die Stringtheorie der Informatik". Als Stringtheoretiker hat sich mein Freund über diese Behauptung gefreut und mich gefragt, was GCT ist. Zu diesem Zeitpunkt wurde mir schändlicherweise klar, dass ich keine wikipedia-fähige Antwort auf seine Frage hatte.

Ich bin mir nicht ganz sicher, welches Niveau für einen Wikipedia-Artikel geeignet ist (verschiedene Artikel scheinen auf unterschiedliche Kompetenzniveaus ausgerichtet zu sein) oder was genau Sie suchen. Also hier ist ein Versuch, aber ich bin offen für Feedback.

Die Theorie der geometrischen Komplexität schlägt vor, die rechnerische Komplexität von Rechenfunktionen (z. B. Polynomen) zu untersuchen, indem die inhärenten Symmetrien der Komplexität und alle zusätzlichen Symmetrien der untersuchten Funktionen ausgenutzt werden.

Wie bei vielen früheren Ansätzen besteht das Endziel darin, zwei Komplexitätsklassen zu trennen, indem gezeigt wird, dass es ein Polynom das Funktionen als Eingaben verwendet (z. B. , durch ihre Koeffizientenvektoren), so dass bei jeder Funktion verschwindet, aber bei einigen Funktionen nicht verschwindet . pfpf∈ C e a s y g h a r d ∈ C h a r $\mathcal{C}_{easy}, \mathcal{C}_{hard}$$p$$f$$p$$f \in \mathcal{C}_{easy}$$g_{hard} \in \mathcal{C}_{hard}$

Die erste Schlüsselidee (vgl. [GCT1, GCT2]) besteht darin, Symmetrien zu verwenden, um nicht die Funktionen selbst zu organisieren, sondern um die ( algebro-geometrischen ) Eigenschaften dieser Funktionen zu organisieren, wie sie durch Polynome wie das obige erfasst werden . Dies ermöglicht die Verwendung der Darstellungstheorie bei dem Versuch, ein solches zu finden . Ähnliche Vorstellungen in Bezug auf Darstellungstheorie und algebraische Geometrie wurden in der algebraischen Geometrie zuvor verwendet, aber meines Wissens nie ganz auf diese Weise.$p$$p$

Die zweite Schlüsselidee (vgl. [GCT6]) besteht darin, kombinatorische (und polynomielle) Algorithmen für die resultierenden darstellungstheoretischen Probleme zu finden und diese Algorithmen dann rückzuentwickeln, um zu zeigen, dass ein solches existiert. Dies kann im Sinne der Verwendung der linearen Programmierung (eines Algorithmus) zum Nachweis bestimmter rein kombinatorischer Aussagen verstanden werden.$p$

In der Tat schlägt [GCT6] vor, die obigen darstellungstheoretischen Probleme auf Ganzzahl-Programmierprobleme zu reduzieren , dann zu zeigen, dass die resultierenden IPs durch ihre LP-Relaxationen gelöst werden, und schließlich kombinatorische Algorithmen für die resultierenden LPs zu liefern. Die Vermutungen in [GCT6] beruhen selbst auf der Rückentwicklung bekannter Ergebnisse für die Littlewood-Richardson-Koeffizienten, ein analoges, aber einfacheres Problem in der Darstellungstheorie. Bei den LR-Koeffizienten stand die kombinatorische Littlewood-Richardson-Regel an erster Stelle. Später gaben Berenstein und Zelevinsky [BZ] sowie Knutson und Tao [KT] (siehe [KT2] für eine freundliche Übersicht) eine IP für LR-Koeffizienten. Knutson und Tao haben auch die Sättigungsvermutung bewiesen, die impliziert, dass die IP durch ihre LP-Relaxation gelöst wird (vgl. [GCT3, BI]).

Die Ergebnisse von [GCT5] zeigen, dass die explizite Derandomisierung des Noether-Normalisierungs-Lemmas im Wesentlichen dem berüchtigten offenen Problem in der Komplexitätstheorie der Black-Box-Derandomisierung von polynomiellen Identitätstests entspricht . Ungefähr so, wie dies in das größere Programm passt, könnte das Finden einer expliziten Basis für die Funktionen , die in (in diesem Fall die Klasse, für die die Determinante vollständig ist) (verschwinden ), sein wird verwendet, um eine kombinatorische Regel für das gewünschte Problem in der Darstellungstheorie abzuleiten, wie dies in anderen Settings der algebraischen Geometrie der Fall war. Ein Zwischenschritt wäre hier, eine Basis für diejenigen zu finden, die bei der Normalisierung von (nicht) verschwindenC e a s y p C e a s $p$$\mathcal{C}_{easy}$$p$$\mathcal{C}_{easy}$ , eine schönere algebraische Variante, mit anderen Worten, um das Noether-Normalisierungs-Lemma für DET zu derandomisieren.

Beispiele für Symmetrien von Komplexität und Funktionen

Zum Beispiel bleibt die Komplexität einer Funktion - für die meisten natürlichen Komplexitätsbegriffe - unverändert, wenn wir die Variablen permutieren durch eine Permutation . Permutationen sind also Symmetrien der Komplexität. Für einige Komplexitätsbegriffe (wie bei algebraischer Schaltungskomplexität) sind alle invertierbaren linearen Änderungen der Variablen Symmetrien.f ( x π ( 1 ) , ... , x π ( n ) ) $f(x_1, \dotsc, x_n)$$f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$$\pi$

Einzelne Funktionen können zusätzliche Symmetrien aufweisen. Beispielsweise hat die Determinante die Symmetrien für alle Matrizen so dass . (Aus dem Wenigen, das ich darüber herausgefunden habe, habe ich herausgefunden, dass dies dem Phänomen des spontanen Symmetriebrechens in der Physik entspricht.)$\det(X)$$\det(AXB) = \det(X^{T}) = \det(X)$$A,B$$\det(AB) = 1$

Einige aktuelle Fortschritte [dieser Abschnitt ist definitiv unvollständig und technischer, aber eine vollständige Darstellung würde Dutzende von Seiten in Anspruch nehmen ... Ich wollte nur einige aktuelle Fortschritte hervorheben]

Burgisser und Ikenmeyer [BI2] zeigten nach dem GCT-Programm eine Untergrenze für die Matrixmultiplikation, sofern Darstellungen mit einer Multiplizität von Null gegen eine Multiplizität ungleich Null verwendet wurden. Landsberg und Ottaviani [LO] gaben die bekannteste Untergrenze von im Wesentlichen für den Grenzrang der Matrixmultiplikation an, indem sie die Darstellungstheorie verwendeten, um algebraische Eigenschaften zu organisieren, aber weder Repräsentationsmultiplizitäten noch kombinatorische Regeln verwendeten.$\frac{3}{2}n^2$$2n^2$

Das nächste Problem nach Littlewood-Richardson-Koeffizienten sind die Kronecker-Koeffizienten . Diese zeigen sich sowohl in einer Reihe von Problemen, von denen vermutet wird, dass sie letztendlich die repräsentationstheoretischen Probleme der GCT erreichen, als auch direkter als Schranken für die Multiplizitäten im GCT-Ansatz zur Matrixmultiplikation und als permanente versus Determinante. Das Auffinden einer kombinatorischen Regel für Kronecker-Koeffizienten ist ein seit langem offenes Problem in der Darstellungstheorie. Blasiak [B] gab kürzlich eine solche kombinatorische Regel für Kronecker-Koeffizienten mit einer Hakenform an.

Kumar [K] zeigte, dass bestimmte Repräsentationen im Koordinatenring der Determinante mit einer Multiplizität ungleich Null auftreten, wenn man die spaltenlateinische Quadrat-Vermutung annimmt (vgl. Huang-Rota und Alon-Tarsi; diese Vermutung taucht auch, vielleicht nicht zufällig, in [BI2 auf ]). Daher können diese Darstellungen nicht verwendet werden, um bleibende von determinanten auf der Grundlage von Multiplizitäten von Null zu Nicht-Null zu trennen, obwohl es immer noch möglich sein könnte, bleibende von determinanten durch eine allgemeinere Ungleichung zwischen Multiplizitäten zu trennen.

Literaturhinweise [B] J. Blasiak. Kronecker-Koeffizienten für eine Hakenform. arXiv: 1209.2018, 2012.

[BI] P. Burgisser und C. Ikenmeyer. Ein Max-Flow-Algorithmus für die Positivität von Littlewood-Richardson-Koeffizienten. FPSAC 2009.

[BI2] P. Burgisser und C. Ikenmeyer. Explizite untere Schranken durch geometrische Komplexitätstheorie. arXiv: 1210.8368, 2012.

[BZ] AD Berenstein und AV Zelevinsky. Dreifache Multiplizitäten für und das Spektrum der Außenalgebra der adjungierten Darstellung. $\mathfrak{sl}(r+1)$J. Algebraic Combin. 1 (1992), no. 1, 7–22.

[GCT1] KD Mulmuley und M. Sohoni. Geometrische Komplexitätstheorie I: Ein Ansatz zum P vs. NP und verwandte Probleme. SIAM J. Comput. 31 (2), 496–526, 2001.

[GCT2] KD Mulmuley und M. Sohoni. Geometrische Komplexitätstheorie II: Auf dem Weg zu expliziten Hindernissen für Einbettungen zwischen Klassensorten. SIAM J. Comput., 38 (3), 1175–1206, 2008.

[GCT3] KD Mulmuley, H. Narayanan und M. Sohoni. Geometrische Komplexitätstheorie III: Über die Entscheidung, keinen Littlewood-Richardson-Koeffizienten zu erhalten. J. Algebraic Combin. 36 (2012), no. 1, 103–110.

[GCT5] KD Mulmuley. Geometrische Komplexitätstheorie V: Äquivalenz zwischen der Blackbox-Derandomisierung des Polynomidentitätstests und der Derandomisierung des Noether-Normalisierungs-Lemmas. FOCS 2012, auch arXiv: 1209,5993.

[GCT6] KD Mulmuley. Geometrische Komplexitätstheorie VI: Der Flip über Positivität. , Technischer Bericht, Institut für Informatik, Universität Chicago, Januar 2011.

[K] S. Kumar. Eine Untersuchung der Darstellungen, die durch die Umlaufbahnschließung der Determinante gestützt werden. arXiv: 1109.5996, 2011.

[LO] JM Landsberg und G. Ottaviani. Neue Untergrenzen für den Randrang der Matrixmultiplikation. arXiv: 1112.6007, 2011.

[KT] A. Knutson und T. Tao. Das Wabenmodell von Tensorprodukten. I. Beweis der Sättigungsvermutung. $\text{GL}_n(\mathbb{C})$J. Amer. Mathematik. Soc. 12 (1999), no. 4, 1055–1090.

[KT2] A. Knutson und T. Tao. Bienenwaben und Summen hermitischer Matrizen. Hinweise Amer. Mathematik. Soc. 48 (2001), no. 2, 175–186.

Ich habe kürzlich eine Antwort auf eine verwandte Frage zu Mathoverflow gegeben: https://mathoverflow.net/questions/277408/was-ist-der-aktuelle- Durchbruch-der-geometrischen-Komplexitätstheorie

Da diese Seite vielleicht ein besserer Veranstaltungsort ist, möchte ich diese Antwort unten wiederholen. Verweise auf Joseph oder Timothy beziehen sich auf die anderen Posts für diese MO-Frage.

---

Es sei eine generische Matrix und der Grad homogenen Polynoms durch die Determinante. Es sei das die Permanent von einer Submatrix und multipliziert mit der von Ihnen bevorzugten linearen Form, um ein weiteres homogenes Polynom vom Grad (man könnte auch den Eintrag anstelle von ). Diese Änderung wird als Auffüllen bezeichnet . Dann definieren Sie die Nummer $X=(X_{ij})_{1\le i,j\le n}$$n\times n$$F_1(X)={\rm det}(X)$$n$

$$F_2(X)=(X_{nn})^{n-m}\times {\rm perm}\left[(X_{ij})_{1\le i,j\le m}\right]$$ $m\times m$$n$$X_{11}$$X_{nn}$ $$c(m)=\min\{\ n\ |\ n\ge m\ \ {\rm and}\ \ \overline{G\cdot F_2}\subset \overline{G\cdot F_1}\ \}$$ wobei wird auf dem affinen Raum der Dimension wirkenden wobei Leben und sind Zariski Schließungen von Orbits. Die große Vermutung in der Gegend oder der Valiant-Hypothese (eine komplexe Version von ) ist, dass schneller wächst als jedes Polynom in .$G$$GL(n^2)$$n^2$$X$$\overline{G\cdot F_i}$${\rm P}\neq{\rm NP}$$c(m)$$m$

Wenn nun , dann hat man eine surjektive äquivariante Abbildung zwischen Grad- Teilen der Koordinatenringe dieser Umlaufbahnschließungen. Das Spiel soll also zeigen, dass dies für nicht ausreichend groß im Verhältnis zu , indem das Vorhandensein einer Multiplizitätsobstruktion , dh einer irreduziblen Darstellung für die Multiplizitäten beweisen.$\overline{G\cdot F_2}\subset \overline{G\cdot F_1}$$G$

$$\mathbb{C}[\overline{G\cdot F_1}]_d\longrightarrow \mathbb{C}[\overline{G\cdot F_2}]_d$$ $d$$n$$m$$\lambda$ $${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)<{\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)$$ oder auf der Ebene der Ideale $${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)>{\rm mult}_{\lambda}(I[\overline{G\cdot F_2}]_d)\ .$$

Ein optimistischer Ansatz ist zu versuchen , gibt es zu zeigen Auftreten Hindernisse , dh ‚s , so dass und . Diese Hoffnung wurde in der von Timothy erwähnten Arbeit von Bürgisser, Ikenmeyer und Panova zunichte gemacht. Die Möglichkeit einer Vielzahl von Behinderungen ist jedoch noch offen.$\lambda$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_1}]_d)=0$${\rm mult}_{\lambda}(\mathbb{C}[\overline{G\cdot F_2}]_d)>0$

Ich denke, der Ansatz von Mulmuley besteht darin, die Existenz solcher Multiplizitätshindernisse zu beweisen, indem alle aus der Darstellungstheorie verfügbaren Werkzeuge für die Berechnung dieser Multiplizitäten genutzt werden. Ich persönlich war noch nie ein Fan dieses Ansatzes. Nachdem ich mich eingehend mit der Invariantentheorie des 19. Jahrhunderts befasst habe, erscheint es mir natürlicher, das Orbitrennungsproblem mit den expliziten Werkzeugen aus dieser Zeit anzugehen. Dieser Artikel von Gorchow scheint auch in eine ähnliche Richtung zu weisen (ich vermute, der dritte Artikel, den Joseph erwähnte, ist in der gleichen Richtung). In der klassischen Sprache (siehe Turnbull oder Littlewood ) muss man explizit einen gemischten Begleiter konstruieren, der mit verschwindet$F_1$aber nicht auf . Dies muss man auch unendlich oft (in ) tun , um die superpolynomiale Wachstumseigenschaft festzustellen. Solch eine Begleiterscheinung ist die gleiche wie eine spezifische Äquivariantenkarte von Ihrem Lieblingsmodell für die irreduzible Repräsentation zur Polynomalgebra in den Variablen (Grochow nennt das ein Trennmodul ). Invariante Theoretiker des 19. Jahrhunderts hatten zwei Methoden, um solche Objekte zu erzeugen: Eliminationstheorie und diagrammatische Algebra .$F_2$$m$$G$$\lambda$$n^2$$X$

Ein sehr kleines Beispiel, in dem und unter der Wirkung von binäre Quartusformen sind (siehe diese MO-Frage ), ist und Eine trennende Begleitgröße (hier tatsächlich eine Kovariante) ist der Hessische Wert eines generischen binären Quarzes Es verschwindet (identisch in ) für aber nicht für$F_1$$F_2$$G=SL(2)$

$$F_1(x,y)=x^4+8x^3y+24x^2y^2+32xy^3+16y^4$$ $$F_2(x,y)=16x^4-24x^3y+12x^2y^2-2xy^3\ .$$ $F$ $$H(F)(x,y)=\frac{\partial^2 F}{\partial x^2}\frac{\partial^2 F}{\partial y^2}-\left( \frac{\partial^2 F}{\partial x\partial y} \right)^2\ .$$ $x,y$$F=F_1$$F=F_2$. In diesem Fall kann das Hessische als eine äquivariante Abbildung aus dem Irreduziblen gesehen werden, das durch die zweite symmetrische Potenz (der grundlegenden zweidimensionalen Darstellung) in den Koordinatenring für den affinen Raum der binären Quartetts gegeben ist.

Ein möglicher superoptimistischer "Plan" für GCT beinhaltet also die folgende Abfolge von Schritten.

1) Finden Sie einen Weg, um Tonnen von Begleitern zu erzeugen.

2) Identifizieren Sie einige explizite Kandidaten für das Verschwinden von und beweisen Sie diese Eigenschaft.$F_1$

3) Zeigen Sie, dass sie auf nicht verschwinden .$F_2$

Schritt 1) ​​wird im Prinzip durch den Ersten Fundamentalsatz für gelöst, aber es gibt eine Fehlpaarung: Die Determinante ist ein natürliches Objekt in der Invariantentheorie für (auf Zeilen einwirkend) und Spalten) statt . Man könnte versuchen , die Abweichung zu reparieren , indem Sie den Grundbaustein für die Invariantentheorie auszudrücken in Bezug auf die eine für (siehe diese MO Frage für eine ähnliche Reduktion Problem von bis ).$GL(n^2)$$GL(n)\times GL(n)$$GL(n^2)$$GL(n^2)$$GL(n)\times GL(n)$$SL(n(n+1)/2)$$SL(n)$

Das Erraten der richtigen Kandidaten für Schritt 2) erscheint mir schwierig. Zuvor zu wissen, dass einige Multiplizitäten ungleich Null sind, würde definitiv helfen. Obwohl man den Beweis des nicht identischen Verschwindens des Begleiters zu Schritt 3) hinausschieben und aufschieben könnte, der sowieso mehr als das zeigen sollte. Wenn man solche richtigen Kandidaten hat, kann es leicht sein , zu zeigen, dass sie auf verschwinden, indem man das Ausschlussprinzip von Pauli (das Zusammenziehen von Symmetrisierungen mit Antisymmetrisierungen), die Eigenschaft hoher chromatischer Zahlen oder einfach "Platzmangel" nennt.${\rm mult}_{\lambda}(I[\overline{G\cdot F_1}]_d)$$F_1$

Ich denke jedoch, der schwierigste Teil ist Schritt 3). In meinem Aufsatz "16.051 Formeln für Ottavianis Invariante von kubischen Dreifachen" mit Ikenmeyer und Royle wurde die Vermutung durch Computersuche getroffen, aber mit dem richtigen Kandidaten in der Hand war das Verschwinden von relativ einfach zu erklären (es ist eher eine hübsches Beispiel für eine chromatische Zahl aufgrund der globalen Eigenschaften des Graphen (anstelle einer großen Clique). Das Analogon von Schritt 3) in unserem Artikel wurde mit Brute-Force-Computern berechnet, und wir haben immer noch keine Ahnung, warum dies der Fall ist. Das paradigmatische Problem im Zusammenhang mit Schritt 3) ist die Alon-Tarsi-Vermutung (siehe diese und diese MO-Frage)$F_1$zu). Meiner Meinung nach muss man bei dieser Art von Frage (auch das Vierfarbensatz ist von diesem Typ, durch eine Reduktion aufgrund von Kauffman und Bar-Natan) vor Valiants Vermutung Fortschritte machen .

Da geht es um Durchbrüche in der GCT. Ich denke , dieser Artikel von Landsberg und Ressayre auch einige Aufmerksamkeit verdient , da es deutet darauf hin , dass eine vernünftige Schätzung für den genauen Wert von ist Beachten Sie, dass Bürgisser und Ikenmeyer in diesem Artikel einen Proof of Concept für den expliziten Ansatz "Schritt 1), 2), 3)" zu einem viel einfacheren Problem gegeben haben . Schließlich empfehle ich für weitere Informationen zu GCT die Übersicht "Geometrische Komplexitätstheorie: eine Einführung für Geometer" von Landsberg.$c(m)$

$$\left(\begin{array}{c}2m\\ m \end{array}\right)-1\ .$$

PS: Ich sollte hinzufügen, dass mein Pessimismus spezifisch für die Valiant-Hypothese ist, die auf diesem Gebiet die Riemann-Hypothese ist. Natürlich sollte man das Baby nicht mit dem Badewasser werfen und GCT verunglimpfen, weil es diese Vermutung bisher nicht bewiesen hat. In diesem Bereich gibt es zahlreiche Probleme, bei denen Fortschritte erzielt wurden und weitere zu erwarten sind. Siehe insbesondere den oben erwähnten Artikel von Grochow und die Rezension von Landsberg.

GCT ist ein Forschungsprogramm zum Nachweis komplexitätstheoretischer Schranken und trotzt aufgrund seiner starken Abstraktion in gewisser Weise einer Zusammenfassung / Zusammenfassung im Wikipedia-Stil, aber für die TCS-Masse sind gute Umfragen verfügbar. [2] [3] [4] (und Wikipedia ist mit Sicherheit der beste Ort für Wikipedia-Einträge). Es wurde in den frühen 2000er Jahren von Mulmuley formuliert und ist sowohl in der Komplexitätstheorie relativ neu als auch sehr fortschrittlich. Es verwendet und wendet fortgeschrittene Mathematik (algebraische Geometrie) an, die nicht aus der TCS / Komplexitätstheorie stammt.

Der Ansatz wird von einigen als vielversprechend, aber möglicherweise von anderen Behörden als zu komplex angesehen, dh es ist nicht bewiesen und daher umstritten, ob er bekannte Standard- "Hindernisse" überwinden könnte. (In diesem Sinne weist es einige Anzeichen eines sogenannten kuhnischen "Paradigmenwechsels" auf.) Sogar Mulmuley schlägt vor, dass es nach Jahrzehnten der Weiterentwicklung realistisch möglicherweise nicht gelingt, größere Komplexitätsklassentrennungen nachzuweisen. Hier ist eine skeptische Meinung von Fortnow, einer führenden Autorität auf dem Gebiet der Komplexitätstheorie:

Stellen Sie sich einen riesigen Berg vor und Sie möchten die Bergspitze erreichen. Ketan kommt vorbei und sagt, dass er dir beibringt, wie man die Werkzeuge für den Aufstieg auf den Berg herstellt. Es wird einen anstrengenden Monat dauern, und tatsächlich sind diese Werkzeuge nicht gut genug, um den Berg zu besteigen. Sie müssen verbessert werden, und diese Verbesserungen werden in Ihrem Leben nicht eintreten. Aber wollen Sie nicht wissen, wie andere in Jahrhunderten den Berg besteigen werden?

[1] Wie man NP anders als P Fortnow Blog prüft

[2] Verständnis des Mulmuley-Sohoni-Ansatzes für P vs. NP Regan

[3] Zu P vs. NP und zur geometrischen Komplexitätstheorie Mulmuley

[4] Das GCT-Programm für das P vs. NP-Problem Mulmuley