Fortgeschrittene Techniken zur Bestimmung der unteren Grenzen der Komplexität

Einige von Ihnen sind möglicherweise dieser Frage gefolgt , die aufgrund mangelnder Forschung abgeschlossen wurde. Ich extrahiere also den Teil der Frage, der sich auf Forschungsebene befindet.

Über die "einfacheren" Techniken hinaus, wie das Reduzieren auf Sortierung oder ein EXPTIME-vollständiges Problem, welche Techniken wurden verwendet, um untere Grenzen für die zeitliche Komplexität eines Problems zu beweisen?

Bestimmtes:

• Was sind die "neuesten" Techniken, die im letzten Jahrzehnt entwickelt wurden?
• Können Techniken aus der Abstrakten Algebra, der Kategorietheorie oder anderen Zweigen der typisch "reinen" Mathematik angewendet werden? (Ich höre zum Beispiel oft die Erwähnung der "algebraischen Struktur" des Sortierens, ohne eine wirkliche Erklärung dessen, was dies bedeutet.)
• Was sind signifikante, aber weniger bekannte Ergebnisse für die Komplexität unterer Grenzen?

Untere Schranken für algebraische Schaltkreise

Bei der Einstellung algebraischer Schaltungen, bei der eine untere Schranke der Schaltungsgröße analog zu einer unteren Schranke der Zeit ist, sind viele Ergebnisse bekannt, bei den moderneren Ergebnissen gibt es jedoch nur wenige Kerntechniken. Ich weiß, dass Sie nach Zeituntergrenzen gefragt haben, aber ich denke, in vielen Fällen besteht die Hoffnung darin, dass die algebraischen Untergrenzen eines Tages zu Booleschen / Turing-Maschinenuntergrenzen führen. Diese Ergebnisse verwenden oft tiefere Techniken aus der "reinen Mathematik", wie Sie es ausdrücken.

I. Der Grad gebunden.

Strassen zeigte, dass das Protokoll des Grades einer bestimmten algebraischen Varietät, die einer (Menge von) Funktion (en) zugeordnet ist, eine Untergrenze für die Größe des algebraischen Schaltkreises zur Berechnung dieser Funktionen darstellt.

II. Verbundene Komponenten (oder allgemeiner die Dimension einer höheren Homologiegruppe).

Ben-Or hat gezeigt, dass die Größe eines realen algebraischen Entscheidungsbaums, der über die Zugehörigkeit zu einer (semi-algebraischen) Menge entscheidet, mindestens wobei C die Anzahl der verbundenen Komponenten dieser Menge ist. Ben-Or hat dies verwendet, um eine untere Grenze von Ω ( n log n ) für die Sortierung (also die Elementunterscheidbarkeit, aber die Elementunterscheidbarkeit reduziert sich auf die Sortierung) im realen algebraischen Entscheidungsbaummodell zu beweisen . Yao erweiterte dies von verbundenen Komponenten auf die Summe der Betti-Zahlen und erwies sich als optimale Untergrenze für andere Probleme (wie k- Gleichungen). In einem anderen Artikel hat Yao dies auf algebraische Entscheidungsbäume über die ganzen Zahlen ausgedehnt.$\log C$$C$$\Omega(n \log n)$$k$

III. Teilweise Ableitungen.

Dies war das Arbeitstier vieler der unteren Schranken moderner algebraischer Schaltkreise. Ich glaube, dass partielle Ableitungen zuerst verwendet wurden, um eine Untergrenze von Baur-Strassen zu beweisen, wo sie zeigten, dass die Berechnung aller ersten Teilwerte von in Größe 5 s erfolgen kann, wobei s die Größe ist, die zur Berechnung von f benötigt wird . In Kombination mit der Gradgrenze von Strassen ergab sich für verschiedene Funktionen eine Untergrenze der Größe von Ω ( n log n ) , die für eine explizite Funktion immer noch die stärkste Untergrenze der Größe uneingeschränkter arithmetischer Schaltkreise darstellt.$f$$5s$$s$$f$$\Omega(n \log n)$

Die neuere Verwendung von partiellen Ableitungen scheint aus einer Arbeit von Nisan zu stammen, in der er die unteren Schranken für nichtkommutative Schaltungen unter Berücksichtigung der Dimension des Raums aller partiellen Ableitungen bewies. Dies wurde verwendet, um von Nisan-Wigderson untere Schranken für eingeschränkte Arten von Tiefen-3-Schaltkreisen zu beweisen, und ähnliche Ideen wurden verwendet, um untere Schranken für die Größe mehrliniger Formeln von Raz (und verwandten Modellen von Raz und Mitarbeitern) zu beweisen. Die jüngsten Tiefen 4 und Tiefen 3 von Gupta, Kayal, Kamath und Saptharishi verwenden eine Verallgemeinerung dieser Idee, um die Dimension des Raums von "verschobenen partiellen Ableitungen" zu zählen - wobei Sie partielle Ableitungen nehmen und dann mit multiplizieren können alle Monome eines bestimmten Grades. ) kann "nur" eine Frage des besseren Verständnisses des von unbefristeten Minderjährigen erzeugten Ideals sein (siehe die Vermutung am Ende ihrer Arbeit).$\mathrm{VP} \neq \mathrm{VNP}$

IV. Gleichungen für Sorten definieren.

Die Idee dabei ist, eine bestimmte algebraische Varietät mit "einfachen Funktionen" zu verknüpfen, Gleichungen zu finden, die für diese Varietät verschwinden, und zu zeigen, dass diese Gleichungen für Ihre "harte Funktion" nicht verschwinden. (Damit wird bewiesen, dass Ihre harte Funktion nicht in der Vielfalt der einfachen Funktionen liegt, so dass sie tatsächlich hart ist.) Besonders nützlich bei unteren Schranken der Matrixmultiplikation. Siehe Landsberg - Ottaviani auf der arXiv für die neuesten Informationen und Verweise auf frühere Untergrenzen.

(Tatsächlich können ich, II und III oben alle als Sonderfälle angesehen werden, in denen definierende Gleichungen für bestimmte Sorten gefunden werden, obwohl die Beweise, die ich, II, III verwenden, im Wesentlichen nie so formuliert werden, da es nicht wirklich eine gab müssen.)

V. Darstellungstheorie, insb. wie in der geometrischen Komplexitätstheorie.

Eigentlich auch von Landsberg-Ottaviani verwendet, um Gleichungen für eine bestimmte Sorte zu finden. Wird auch von Burgisser-Ikenmeyer verwendet, um einen "rein" darstellungstheoretischen Beweis für eine etwas schwächere Untergrenze der Matrixmultiplikation zu erhalten. Von Mulmuley und Sohoni vermutet (vgl. "Geometric Complexity Theory I & II"), dass es nützlich ist, gegen V N P und letztendlich N P gegen P / p o l y aufzulösen .$\mathrm{VP}$$\mathrm{VNP}$$\mathrm{NP}$$\mathrm{P/poly}$

Kaveh hat in seiner Antwort sanft angedeutet, dass ich etwas sagen sollte. Ich habe sonst nicht viel zu dieser schön umfassenden Liste von Antworten beizutragen. Ich kann ein paar allgemeine Worte darüber hinzufügen, wie sich die unteren Grenzen der "strukturellen Komplexität" in den letzten zehn Jahren oder so entwickelt haben. (Ich benutze den Namen "strukturelle Komplexität" nur, um zwischen Algebra, Kommunikationskomplexität usw. zu unterscheiden.)

Die gegenwärtigen Ansätze basieren noch weitgehend auf der Diagonalisierung und insbesondere auf dem folgenden grundlegenden Paradigma: Beginnen Sie mit der Annahme des Gegenteils der Untergrenze. Dies gibt Ihnen einen schönen Algorithmus für ein Problem. Versuchen Sie, diesen Algorithmus zu verwenden, um einem Hierarchiesatz zu widersprechen, der auf der Diagonalisierung basiert, z. B. der Zeit- oder Raumhierarchie. Da Diagonalisierungsargumente allein nicht ausreichen, um neue Untergrenzen zu beweisen, werden der Mischung andere Zutaten hinzugefügt, um das widersprüchliche Rezept zu erhalten.

Ich sollte sagen, dass viele Argumente aus den 70er und 80er Jahren dem obigen Muster folgen; Der Hauptunterschied heutzutage sind die "anderen Zutaten" - es gibt viele Zutaten zur Auswahl, und die Art und Weise, wie Zutaten angewendet werden können, scheint nur durch Ihre eigene Kreativität begrenzt zu sein. Manchmal, wenn Sie nicht wissen, wie man bestimmte Zutaten mischt, um ein besseres Rezept zu erhalten, aber Sie genau wissen, wie sie sich mischen lassen, ist es hilfreich, ein Computerprogramm zu programmieren, das Ihnen neue Rezepte vorschlägt.

Es wäre sehr interessant, neue Beweise für die jüngsten Untergrenzen zu erhalten, die definitiv nicht diesem Paradigma folgen. Kann zum Beispiel ohne Bezugnahme auf ein Diagonalisierungsargument bewiesen werden? Kann dies zunächst bewiesen werden, ohne auf den Satz der nicht deterministischen Zeithierarchie zurückzugreifen? (Könnte man stattdessen zum Beispiel die "Schaltkreisgrößenhierarchie" verwenden?)$NEXP \not\subset ACC$

$\Omega(n \log n)$Die untere Grenze für die Sortierung funktioniert nur für vergleichsbasierte Sortieralgorithmen. Ohne diese Einschränkung und in allgemeineren Berechnungsmodellen kann die Sortierung möglicherweise schneller gelöst werden, sogar in linearer Zeit. (Siehe Joshs Kommentar unten.)

Hier sind einige grundlegende direkte Methoden zum Nachweis von Untergrenzen in der rechnerischen Komplexitätstheorie für die allgemeineren Rechenmodelle (Turing-Maschinen und -Schaltungen).

I. Zählen:

Idee: Wir zeigen, dass es mehr Funktionen als Algorithmen gibt.

Bsp .: Es gibt Funktionen, die exponentiell große Schaltkreise erfordern.

Das Problem bei dieser Methode ist, dass es sich um ein existenzielles Argument handelt und keine explizite Funktion oder Obergrenze für die Komplexität des Problems gibt, die sich als schwierig erwiesen hat.

II. Kombinatorisch / Algebraisch:

Idee: Wir analysieren die Schaltkreise und zeigen, dass sie eine bestimmte Eigenschaft haben, z. B. können die von ihnen berechneten Funktionen durch eine nette Klasse von mathematischen Objekten angenähert werden, während die Zielfunktion diese Eigenschaft nicht hat.

$\mathsf{AC^0}$$\mathsf{AC^0}[p]$

Das Problem bei dieser Methode ist, dass sie in der Praxis nur für kleine und relativ einfach zu analysierende Klassen funktioniert hat. Es gibt auch Razborov-Rudichs Natural Proofs- Barriere, die in gewisser Weise formalisiert, warum einfache Eigenschaften für sich allein wahrscheinlich nicht ausreichen, um allgemeinere Schaltkreisuntergrenzen zu beweisen.

Razborovs Arbeit " Über die Methode der Approximation " argumentiert, dass die Approximationsmethode vollständig ist, um untere Grenzen in gewissem Sinne zu beweisen.

III. Diagonalisierung:

Idee. Wir diagonalisieren gegen die Funktionen in der kleineren Klasse. Die Idee geht auf Gödel (und sogar Cantor) zurück.

Ex. Zeithierarchiesatz , Raumhierarchiesatz usw.

$\mathsf{P}$$\mathsf{PSpace}$$\mathsf{P}$$\mathsf{PSpace}$

Wir haben auch die Relativierungsbarriere (zurückgehend auf Baker, Gill und Solovay) und die Algebraisierungsbarriere (von Aaronson und Wigderson), die besagen, dass bestimmte Arten von Diagonalisierungsargumenten auf andere Settings übertragen werden, in denen das Ergebnis nachweislich falsch ist.

Beachten Sie, dass diese Barrieren nicht für allgemeinere Diagonalisierungsargumente gelten. Tatsächlich ist nach Dexter Kozens Aufsatz " Indexing of subrecursive classes " die Diagonalisierung abgeschlossen, um untere Schranken zu beweisen.

Wie Sie wahrscheinlich bemerkt haben, besteht ein enger Zusammenhang zwischen der Suche nach guten universellen Simulatoren für eine Komplexitätsklasse und der Trennung dieser Komplexitätsklasse von größeren Klassen (eine formelle Aussage finden Sie in Kozens Artikel).

Neueste Werke

Informationen zu den jüngsten Fortschritten finden Sie in den neuesten Veröffentlichungen von Ryan Williams . Ich diskutiere sie in dieser Antwort nicht, da ich hoffe, dass Ryan selbst eine Antwort schreiben wird.

Algebraische Entscheidungsbäume

Dies ist keine neuere Technik, aber eine, die für bestimmte Probleme ziemlich leistungsfähig ist.

$n$$d$

• $v$$q_v(x_1, \dots, x_n)$$d$$x_i-x_j$$i$$j$

• $-1$$0$$+1$

• $\{1,2,\dots,n\}$

$\vec{x}\in\mathbb{R}^n$

$\Omega(n^d)$

$\ell$$R(\ell) \subseteq \mathbb{R}^n$$\ell$$R(\ell)$$\mathbb{R}^n$$t = \text{depth}(\ell)$$d$$d$$(dt)^{O(n)}$

$W\subseteq\mathbb{R}^n$$d$$t$$W$$3^t (dt)^{O(n)}$$t = \Omega(\log \#W - n\log d)$

$n$$W$$n!$$n$$\Omega(n\log n)$

$\Omega(n\log n)$

$R(\ell)$$(dt)^{O(n)}$

$n^{O(n)}$$n\log n$

$\Omega(n^2)$$O(n^4\log n)$$2^{O(n)}$$\mathbb{R}^n$. Somit ist es unmöglich, untere Grenzen größer als zu beweisen$n^4\log n$$k$$k$$k$$k$$O(n^{k/2})$$O(n^4\log n)$Abfragepolynome; Diese Konstruktionszeit ist im unteren Modell frei.

Hurra für doppelt negative Ergebnisse!

Manindra Agrawal hat ein nettes Paper "Lower Bounds mittels Pseudozufallsgeneratoren beweisen". Dies könnte als "dunkles Pferd" im Rennen angesehen werden, um untere Schranken zu beweisen, aber das Papier ist interessant.

Dies ist eine 32p-Umfrage, die gerade zu dem Thema erschien, das sich auf den unteren Grenzwinkel der Schaltung konzentriert (hier gibt es starke Überschneidungen im Inhalt mit anderen Antworten).

• Algorithmen versus Circuit Lower Bounds von Oliveira

Verschiedene Techniken wurden verwendet, um mehrere Übertragungssätze der Form "nicht-triviale Algorithmen für eine Schaltungsklasse C ergeben Schaltungsuntergrenzen gegen C" zu beweisen. In dieser Umfrage überprüfen wir viele dieser Ergebnisse. Wir diskutieren, wie Schaltungsuntergrenzen durch Derandomisierungs-, Komprimierungs-, Lern- und Erfüllbarkeitsalgorithmen erhalten werden können. Wir behandeln auch den Zusammenhang zwischen Schaltkreisuntergrenzen und nützlichen Eigenschaften, ein Begriff, der sich im Kontext dieser Übertragungssätze als grundlegend herausstellt. Dabei erhalten wir einige neue Ergebnisse, vereinfachen mehrere Beweise und zeigen Zusammenhänge mit unterschiedlichen Frameworks. Wir hoffen, dass unser Vortrag eine in sich geschlossene Einführung für alle darstellt, die sich für Forschung auf diesem Gebiet interessieren.