Gaußsche Eliminierung in Bezug auf Gruppenaktionen

Die Gaußsche Eliminierung macht die Determinante einer Matrixpolynomzeit berechenbar. Die Verringerung der Komplexität bei der Berechnung der Determinante, die ansonsten die Summe der Exponentialausdrücke ist, beruht auf dem Vorhandensein alternativer negativer Vorzeichen (deren Fehlen die Berechnung permanent macht, ist $\#P\mbox{-}hard$ dh härter als $NP\mbox{-}C$ Probleme). . Dies führt zu einer Art Symmetrie in der Determinante, z. B. wenn ein Paar Zeilen oder Spalten ausgetauscht wird, werden die Vorzeichen einfach umgekehrt. Ich habe irgendwo gelesen, wahrscheinlich im Zusammenhang mit den von Valiant eingeführten holographischen Algorithmen, dass die Gaußsche Eliminierung in Form von Gruppenaktionen erklärt werden kann, was wiederum zu allgemeinen Techniken zur Reduzierung der Komplexität führt.

Ich glaube auch, dass fast jede Quelle der Komplexitätsreduzierung für ein Rechenproblem eine Art von Symmetrie ist. Ist es wahr? Können wir dies in Bezug auf die Gruppentheorie konsequent formalisieren?

Bearbeiten

Ich habe die Referenz gefunden . (Seite 2, letzte Zeile des zweiten Absatzes). Ich habe das Papier nicht richtig verstanden. Wenn meine Frage auf einem falschen Verständnis des Papiers beruht, korrigieren Sie mich bitte.

Im Fall der Determinante kann die Gaußsche Eliminierung tatsächlich als äquivalent zu der Vorstellung angesehen werden, dass die Determinante eine große Symmetriegruppe (einer bestimmten Form) aufweist und durch diese Symmetriegruppe (dh ein beliebiges anderes homogenes Polynom in n $n$$n^2$ -Variablen) gekennzeichnet ist mit diesen Symmetrien muss ein skalares Vielfaches der Determinante sein). (Und in Bezug auf @Tsuyoshi Itos Punkt, dass die Symmetrien der bleibenden Karte nicht dazu beitragen, sie effizient zu berechnen: Obwohl die bleibende Karte auch durch ihre Symmetrien gekennzeichnet ist, ist ihre Symmetriegruppe viel kleiner als die der Determinante.)

Eine Zusammenfassung davon - wobei die Symmetrien der Determinante zur Gaußschen Eliminierung herangezogen werden und der Beweis erbracht wird, dass die Determinante durch ihre Symmetrien charakterisiert ist - finden Sie in Satz 3.4.3 meiner These (Schamloser Selbstpfropfen) Ich habe es auch noch nie so formuliert und ausführlich geschrieben gesehen, wie es das OP verlangt hat, obwohl ich mir sicher bin, dass es getan wurde. Ich wäre froh, wenn jemand andere Referenzen hätte.

Zu der Idee, dass Symmetrie immer zu einer Reduzierung der Komplexität führt (oder auch nicht), lesen Sie zusätzlich zu den bereits in den Kommentaren enthaltenen Dingen diese Frage und ihre Antworten.

Ein interessanter Punkt ist, dass er in Valiants ersten Arbeiten über die heutige Valiantsche Version der algebraischen Komplexitätstheorie den Punkt anstrebte, dass ein Grund, warum die Determinante rechnerisch wichtig ist, darin besteht, dass ungefähr alle (damals) bekannten effizienten Algorithmen vorhanden sein könnten reduziert auf lineare Algebra und von da an auf die Berechnung der Determinante, zB des FKT-Algorithmus zur Zählung von Matchings in planaren Graphen. Dies ist natürlich übertrieben, wird aber weiterhin durch die Erforschung holographischer Algorithmen untermauert, die sich häufig auf die Berechnung des Pfaffian (eines engen Verwandten der Determinante) beschränken. Sicher wusste Valiant, dass dies eine Übertreibung war, aber hier ist das genaue Zitat, um sicherzustellen, dass ich nicht falsch dargestellt werde ( L. Valiant. Vollständigkeitsklassen in Algebra. ACM STOC 1979 ):

Unsere wichtigsten Schlussfolgerungen lassen sich grob wie folgt zusammenfassen:

(a) Die lineare Algebra ist im Wesentlichen die einzige schnelle Methode zur Berechnung multivariater Polynome mäßigen Grades

(b) ...

Es gibt Fälle, in denen die Symmetrien eines Problems seine Komplexität charakterisieren (scheinen). Ein sehr interessantes Beispiel sind Constraint-Zufriedenheitsprobleme (CSPs).

Definition von CSP

$U$$\Gamma$$k$$U^k$$\{0, 1\}$$V$$\Gamma$$\phi:V \rightarrow U$ so dass alle Bedingungen erfüllt sind.

$\Gamma$$U$$\{0, 1\}$$\Gamma$$k$$U$$\{0, 1\}$

Polymorphismen

$\phi_1, \ldots, \phi_t$$f:U^t \rightarrow U$$\phi$$\phi(v) = f(\phi_1(v), \ldots, \phi_t(v))$$f$$t$

$f(x, y, z) = x + y + z \pmod 2$$f(x, x, y) = f(y, x, x) = y$$f$ , das diese Eigenschaft erfüllt, wird als Maltsev-Operation bezeichnet. CSPs mit Maltsev-Polymorphismus sind durch Gauß-Eliminierung lösbar.

$f(x, y) = x$

Polymorphismen und Komplexität (die Dichotomie-Vermutung)

$\Gamma_1$$\Gamma_2$$\Gamma_1$$\Gamma_2$$\Gamma_2$$\Gamma_1$ in der Tat schwieriger ist.

Ein großes offenes Problem in der Komplexitätstheorie ist die Charakterisierung der Härte von CSPs. Die Dichotomie-Vermutung von Feder und Vardi besagt, dass jeder CSP entweder P- oder NP-vollständig ist. Die Vermutung lässt sich auf eine Aussage über Polymorphismen reduzieren: Ein CSP ist genau dann NP-hart, wenn die einzigen Polymorphismen, die er zulässt, "Diktatoren" sind (ansonsten ist es in P). Das heißt, ein CSP ist nur dann schwierig, wenn es vor Ort keine Möglichkeit gibt, aus alten Lösungen echte neue Lösungen zu bilden. Der if-Teil (Härte) ist bekannt, aber der einzige if-Teil (Entwurf eines Polytime-Algorithmus) ist offen.

$U = \{0, 1\}$

Um mehr über Polymorphismen, Universalalgebra und die Dichotomie-Vermutung zu erfahren, schauen Sie sich die Umfrage von Bulatov an .

Polymorphismen und Approximierbarkeit

Ich empfehle auch einen IAS-Vortrag von Prasad Raghavendra, in dem er sein Ergebnis präsentiertunter der Annahme der Vermutung, dass es sich um ein einzigartiges Spiel in einem ähnlichen Rahmen handelt, eine optimale Approximierbarkeit jedes CSP zu erzielen. Wenn alle Polymorphismen (die zur Behandlung von Approximationsproblemen verallgemeinert werden müssen) eines CSP in der Nähe von Diktatoren liegen, kann mit dem CSP eine Möglichkeit entworfen werden, um zu testen, ob eine Funktion ein Diktator ist Sei alles, was du brauchst, um eine Annäherungsverringerung von einzigartigen Spielen zu erreichen. Dies gibt die Richtung der Härte seines Ergebnisses an; Die algorithmische Richtung ist, dass, wenn ein CSP einen Polymorphismus hat, der weit von einem Diktator entfernt ist, man ein Invarianzprinzip (Verallgemeinerung zentraler Grenzwertsätze) verwenden kann, um zu argumentieren, dass ein SDP-Rundungsalgorithmus eine gute Annäherung ergibt. Eine wirklich skizzenhafte Intuition für den algorithmischen Teil: Ein Polymorphismus, der weit von einem Diktator entfernt ist. Es ist egal, ob es sich um Argumente (eine Verteilung über) Variablenzuweisungen oder um Gauß-Zufallsvariablen handelt, die sich lokal einer Verteilung über Variablenzuweisungen annähern. Dies ist die gleiche Weise, wie es eine Summenfunktion "nicht interessiert", wenn sie diskrete Zufallsvariablen mit kleiner Varianz oder Gaußsche rvs mit derselben Varianz gemäß dem zentralen Grenzwertsatz erhält. Die benötigten Gaußschen Zufallsvariablen können aus einer SDP-Relaxation des CSP-Problems berechnet werden. Also finden wir einen Polymorphismus, der weit von einem Diktator entfernt ist, füttern ihn mit den Gaußschen Proben und erhalten eine gute Lösung zurück. wenn es diskrete Zufallsvariablen mit kleiner Varianz oder Gaußsche rvs mit derselben Varianz nach dem zentralen Grenzwertsatz gibt. Die benötigten Gaußschen Zufallsvariablen können aus einer SDP-Relaxation des CSP-Problems berechnet werden. Also finden wir einen Polymorphismus, der weit von einem Diktator entfernt ist, füttern ihn mit den Gaußschen Proben und erhalten eine gute Lösung zurück. wenn es diskrete Zufallsvariablen mit kleiner Varianz oder Gaußsche rvs mit derselben Varianz nach dem zentralen Grenzwertsatz gibt. Die benötigten Gaußschen Zufallsvariablen können aus einer SDP-Relaxation des CSP-Problems berechnet werden. Also finden wir einen Polymorphismus, der weit von einem Diktator entfernt ist, füttern ihn mit den Gaußschen Proben und erhalten eine gute Lösung zurück.